Description

在兄贵们居住的异次元幻想乡——新日暮里，比利王和香蕉君两位哲学家正面临一场危机！

暗黑大将军 VAN 样通过奥义「Deep♂Dark♂Fantasy」污染了哲学能量核心，导致整个世界的男魂符号「♂」陷入混乱。为了拯救新日暮里，两位哲学家想要去穿越那扇藏在「VANの神殿」深处的「哲学之门」，传说只有集齐所有「哲学密钥」的兄贵，才能解开「哲学之门」的封印，获得「东方馅挂炒饭」的终极配方，阻止暗黑大将军的阴谋。然而，这扇门的钥匙被分割成碎片，散落在「VANの神殿」的迷宫中！

危难之际，两位哲学家打破了第 ⑨ 面墙，在电子科技大学这块充满灵性的土地上，找到了热衷于 xcpc 竞赛的你，相信拥有高超计数能力的你，一定可以在迷宫中找齐所有「哲学密钥」，用「东方馅挂炒饭」拯救陷入混乱的幻想乡！

「VANの神殿」的迷宫是一张由 $n$ 个点 $m$ 条边组成的无向图，这张图中的每个点度数不超过三（即与每个点相邻的边不超过三条），且保证不出现重边与自环。你需要统计出这张图中形如「哲学密钥」的连通子图数量。「哲学密钥」是一个包含九个点九条边的连通子图，且九个点需要按照如图所示的位置关系进行连边（图中点的编号仅做参考）。

注意：每条边和每个点可以属于多个不同的「哲学密钥」子图。两个连通子图被视为不同的「哲学密钥」当且仅当两个子图中的边集不完全相同。

Input

第一行一个整数 $T$（$1 \leq T \leq 10^4$），表示测试数据组数。

对于每组数据，第一行输入两个整数 $n, m$ ($2 \leq n \leq 10^5$, $1 \leq m \leq 1.5 n$)，表示迷宫的点数与边数，接下来 $m$ 行每行输入两个整数 $x,y$ ($1 \leq x,y \leq n$) ，表示 $x$ 与 $y$ 之间有一条无向边，数据保证 $x\ne y$。

保证所有测试数据 $n$ 之和不超过 $10^5$。

Output

对于每组数据，你需要输出一行一个整数，表示不同的「哲学密钥」连通子图数量。

Samples

2
11 12
1 2
2 3
3 4
4 5
5 6
6 1
6 7
7 8
7 9
10 11
10 3
10 2
9 11
1 2
2 3
3 4
4 5
5 6
6 1
6 7
7 8
7 9
5 9
8 9

1
2

Resources

The 23rd UESTC Programming Contest Preliminary