Leshphon 曾经是 Byteland 一个宁静而美丽的村庄，直到讨厌的疾病降临。Leshphon 有 $n$ 个区域，由 $m$ 条有向道路连接，使得你可以从任何一个区域通过这些有向道路到达其他所有区域。换句话说，它是强连通的。

为了控制传染源并切断传播途径，Byteland 政府决定在 Leshphon 关闭恰好三条有向道路，使得该村庄不再是强连通的。可能存在多种解决方案，你能算出它们的总数吗？

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10$)，表示测试用例的数量。对于每个测试用例：

第一行包含两个整数 $n$ 和 $m$ ($3 \le n \le 50, 3 \le m \le n(n - 1)$)，分别表示区域的数量和道路的数量。

接下来的 $m$ 行，每行包含两个整数 $u_i$ 和 $v_i$ ($1 \le u_i, v_i \le n, u_i \neq v_i$)，描述一条从第 $u_i$ 个区域到第 $v_i$ 个区域的有向道路。

保证该村庄是强连通的，且给定的 $m$ 条道路互不相同。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示解决方案的总数。

样例

输入 1

1
4 7
1 2
2 3
3 4
4 1
1 3
2 4
3 1

输出 1

34