Arona and Plana are good friends; they can resolve anything through friendly negotiation.

One morning, Arona opened the fridge and found that there was only one strawberry milk left! She thought Plana would steal her milk, so she challenged Plana to a duel! The duel is as follows:

Arona chooses a positive integer $n$, then randomly chooses a permutation $a$ of $1, 2, \cdots, n$. Let $L$ denote the number of positive integers $i$ such that $\max\limits_{j=1}^i a_j = a_i$, and let $R$ denote the number of positive integers $i$ such that $\min\limits_{j=1}^i a_j = a_i$. If $L \ge R$, then Arona wins; otherwise Plana wins.

Arona is very confident and thinks she can easily win. To prevent Plana from complaining that the game is unfair when she wins, she also chose a positive integer $k \le n$ and changed her winning condition to $L \ge R + k$.

Although Plana does not care about the strawberry milk at all, she knows that Arona's probability of winning is not very high. Plana now wants to know exactly what this probability is. Can you, on the other side of the screen, help her compute this exact value?

Suppose the probability that Arona can win is $p$. You only need to compute $p \times n!$ modulo $998244353$.

Input

This problem contains multiple test cases.

The first line contains a positive integer $T$ $(1 \le T \le 10^3)$, denoting the number of test cases.

The next $T$ lines each contain two integers $n, k$ $(1 \le k \le n \le 10^6)$, whose meanings are the same as in the statement.

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

Output

For each test case, output a line containing one integer, the required answer modulo $998244353$.

Examples

Input 1

2
3 1
3 2

Output 1

2
1

Input 2

10
5 3
97 31
2468 1357
9876 1
9876 1234
9876 6789
234567 1
234567 234555
234567 123456
234567 12345

Output 2

7
878338345
199045303
782408107
474021604
653690172
358465928
130271340
136329270
679313091

Note

For the first set of sample data, when $n = 3$, there are $6$ permutations in total:

• Sequence $[1, 2, 3]$: $L = 3, R = 1$.
• Sequence $[1, 3, 2]$: $L = 2, R = 1$.
• Sequence $[2, 1, 3]$: $L = 2, R = 2$.
• Sequence $[2, 3, 1]$: $L = 2, R = 2$.
• Sequence $[3, 1, 2]$: $L = 1, R = 2$.
• Sequence $[3, 2, 1]$: $L = 1, R = 3$.

Therefore, when $n = 3, k = 1$, the permutations $[1, 3, 2]$ and $[1, 2, 3]$ satisfy $L \ge R + 1$; when $n = 3, k = 2$, only $[1, 2, 3]$ satisfies $L \ge R + 2$.