On Planet E, people travel by horses!
There are $n$ cities on Planet E, labeled $0, 1, \\dots, n -1$, and $m$ roads connecting the cities. For each $j = 0, 1, \\dots, m -1$, road $j$ connects city $x_j$ and city $y_j$, meaning that we can travel from city $x_j$ to city $y_j$ (and from city $y_j$ to city $x_j$) in one step. Note that $x_j$ can be the same as $y_j$, meaning that both ends of the road is city $x_j$.
Now the people on Planet E wants to build some stable for the horses. However the horses on Planet E has a strange habit: they must move exactly $k$ steps everyday. For each step, a horse must choose one of the roads that connects to its current city, and moves to the city on other end of the road. Hence we shall only build stables at city $i$ if a horse at city $i$ can move back to city $i$ after $k$ steps.
Can you help the people on Planet E to determine how many cities they can build stables at?
The first line contains a positive integer $T$ ($T <= 20$), the number of testcases.
Each testcase starts with a line consisting of three integers $n, m, k$ ($1 <= n <= 50$, $0 <= m <= 2500$, $0 <= k <= 10^9$), the number of cities and roads, and the number of steps a horse must move everyday. Then there are $m$ lines followed, each consisting of two integers $x_j, y_j$ ($0 <= x_j <= n -1$, $0 <= y_j <= n -1$), meaning that the $j$-th road connects city $x_j$ and city $y_j$.
For each testcase, output a single line consisting of the number of cities that can have a stable built.
In the last testcase, we can build stables at every cities but city $3$.
City $0$: $0 arrow.r 1 arrow.r 2 arrow.r 0 arrow.r 1 arrow.r 0$.
City $1$: $1 arrow.r 2 arrow.r 0 arrow.r 1 arrow.r 2 arrow.r 1$.
City $2$: $2 arrow.r 0 arrow.r 1 arrow.r 2 arrow.r 0 arrow.r 2$.
City $4$: $4 arrow.r 0 arrow.r 1 arrow.r 2 arrow.r 0 arrow.r 4$.
## Input
The first line contains a positive integer $T$ ($T <= 20$), the number of testcases.Each testcase starts with a line consisting of three integers $n, m, k$ ($1 <= n <= 50$, $0 <= m <= 2500$, $0 <= k <= 10^9$), the number of cities and roads, and the number of steps a horse must move everyday. Then there are $m$ lines followed, each consisting of two integers $x_j, y_j$ ($0 <= x_j <= n -1$, $0 <= y_j <= n -1$), meaning that the $j$-th road connects city $x_j$ and city $y_j$.
## Output
For each testcase, output a single line consisting of the number of cities that can have a stable built.
[samples]
## Note
In the last testcase, we can build stables at every cities but city $3$.City $0$: $0 arrow.r 1 arrow.r 2 arrow.r 0 arrow.r 1 arrow.r 0$.City $1$: $1 arrow.r 2 arrow.r 0 arrow.r 1 arrow.r 2 arrow.r 1$.City $2$: $2 arrow.r 0 arrow.r 1 arrow.r 2 arrow.r 0 arrow.r 2$.City $4$: $4 arrow.r 0 arrow.r 1 arrow.r 2 arrow.r 0 arrow.r 4$.
**Definitions**
Let $ G = (V, E) $ be an undirected graph with $ V = \{0, 1, \dots, n-1\} $ and $ E \subseteq V \times V $, where each edge $ (x_j, y_j) \in E $ represents a bidirectional road. Let $ A \in \{0,1\}^{n \times n} $ be the adjacency matrix of $ G $, with $ A_{i,j} = 1 $ if $ (i,j) \in E $, else $ 0 $.
**Constraints**
1. $ 1 \leq n \leq 50 $
2. $ 0 \leq m \leq 2500 $
3. $ 0 \leq k \leq 10^9 $
4. $ T \leq 20 $
**Objective**
For each test case, compute the number of cities $ i \in V $ such that there exists a walk of exactly $ k $ steps starting and ending at $ i $. This is equivalent to computing the number of indices $ i $ for which $ (A^k)_{i,i} > 0 $.
Output:
$$
\left| \left\{ i \in \{0, 1, \dots, n-1\} \mid (A^k)_{i,i} > 0 \right\} \right|
$$