Leshphon

Problem Description

Leshphon was a peaceful and beautiful village in Byteland until the nasty disease came here. There are $n$ districts in Leshphon, connected by $m$ directed roads such that you can reach every other district from any district via these directed roads. In other words, it is strongly connected. To control the sources of infection and cut off the channels of transmission, the government of Byteland decides to close exactly three directed roads in Leshphon, such that the village is not strongly connected anymore. There may be many possible solutions, can you figure out the total number of them?

Input

The first line contains a single integer $T$ ($1 \leq T \leq 10$), the number of test cases. For each test case: The first line contains two integers $n$ and $m$ ($3\leq n\leq 50$, $3\leq m\leq n(n-1)$), denoting the number of districts and the number of roads. Each of the following $m$ lines contains two integers $u_i$ and $v_i$ ($1 \leq u_i,v_i\leq n$, $u_i\neq v_i$), describing a directed road from the $u_i$-th district to the $v_i$-th district. It is guaranteed that the village is strongly connected, and all the given $m$ roads are pairwise different.

Output

For each test case, output a single line containing an integer, denoting the number of solutions.

Sample Input

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

Sample Output

34

Source

2023“钉耙编程”中国大学生算法设计超级联赛（3）