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