A clique is a complete graph, in which there is an edge between every pair of the vertices. Given a graph with $N$ vertices and $M$ edges, your task is to count the number of cliques with a specific size $S$ in the graph.

Input

The first line is the number of test cases. For each test case, the first line contains 3 integers $N$, $M$ and $S$ ($N \le 100$, $M \le 1\,000$, $2 \le S \le 10$), each of the following $M$ lines contains 2 integers $u$ and $v$ ($1 \le u < v \le N$), which means there is an edge between vertices $u$ and $v$. It is guaranteed that the maximum degree of the vertices is no larger than 20.

Output

For each test case, output the number of cliques with size $S$ in the graph.

Example

Input

3
4 3 2
1 2
2 3
3 4
5 9 3
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
6 15 4
1 2
1 3
1 4
1 5
1 6
2 3
2 4
2 5
2 6
3 4
3 5
3 6
4 5
4 6
5 6

Sample Output

3
7
15