Statement : E2. Graph Cutting (Two Vertices, All Pairs)

Pair version of E. Graph Cutting. Fedya chooses two distinct vertices $a, b$ ($a \lt b$) and cuts the minimal connected subgraph containing both. Count pairs whose cut has size exactly $d$. Warmups: E0 / E1. Triplet chain: E3 → E4 → E.

The first line contains an integer $t$ ($1 \le t \le 500$).

Each test case:

• One line: $n$ and $d$ ($2 \le d \le n \le 2000$).
• Then $n - 1$ lines: tree edges.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2000$.

For each test case, print the number of unordered pairs $(a,b)$ with $1 \le a \lt b \le n$ such that the minimal connected subgraph containing $a$ and $b$ has exactly $d$ vertices, modulo $998244353$.

Input

3
4 3
1 2
3 1
4 1
5 5
1 2
2 4
2 3
5 1
7 7
1 2
1 3
2 4
2 5
3 6
3 7

Output

3
1
0

Note

These are the same trees as in E, but we count pairs instead of triples.

• Test 1 (star on $4$ vertices): pairs at distance $2$ are $(2,3)$, $(2,4)$, $(3,4)$ — each path has $3$ vertices. Answer $3$.
• Test 2: the longest path has $4$ vertices (e.g. $3 \text{–} 2 \text{–} 1 \text{–} 5$), so no pair has minimal cut size $5$. Answer $0$. (The full E answer is $1$ because triple $(3,4,5)$ spans the whole tree.)
• Test 3: no pair is at distance $6$.