Problem Statement

There is a complete graph with $N$ vertices.
The $M=N(N-1)/2$ edges of this graph are numbered $i=1,2,\dots,M$ and are distinguishable from each other.

Initially, all $M$ edges are white.
You choose some of the $M$ edges and paint each of them red, blue, or purple (you cannot paint $1$ edge with multiple colors).
How many colorings satisfy all of the following conditions?

• The numbers of red, blue, and purple edges are $N-1-K,N-1-K,K$, respectively, and the remaining edges stay white.
• The graph obtained by keeping only the $N-1$ edges that are red or purple is a tree.
• The graph obtained by keeping only the $N-1$ edges that are blue or purple is a tree.

Here, $2$ colorings are considered different if there exists at least $1$ edge $i\ (1\le i \le M)$ whose color differs between them.
Since the answer can be very large, find it modulo $998244353$.

For each input, answer $T$ test cases.

Constraints

• $1 \le T \le 5\times 10^5$
• $2 \le N \le 2000$
• $0 \le K \le N-1$
• All inputs are integers.

Input

First, the number of test cases $T$ in the input is given on line $1$.

$T$

Then, $T$ test cases are given over the following $T$ lines. Each test case is given on $1$ line in the following format.

$N\ \ K$

Output

Output $T$ lines.
On line $i$ $(1\le i \le T)$, output the answer to the $i$-th test case.

Sample

12
2 0
2 1
3 0
3 1
3 2
4 0
4 1
4 2
4 3
10 9
314 159
1883 1014

0
1
0
6
3
12
120
108
16
100000000
771532131
812345678