zzq has several bags of coins, each containing $k$ coins. One bag consists entirely of fake coins, while all other bags consist of genuine coins. Fake coins and genuine coins are identical in every way except for their weight; fake coins are heavier, and coin weights are positive real numbers.

zzq has an electronic scale and intends to perform $m$ weighings. Formally, for each weighing, zzq can specify two disjoint sets of coins $A$ and $B$, and the scale will output the exact value of $W(A) - W(B)$, where $W(A)$ denotes the total weight of the coins in set $A$. The coins used in the weighings can come from any of the bags.

zzq is lazy, so he wants you to help him provide a weighing plan using at most $m$ weighings to determine which bag contains the fake coins. The weighing plan you provide must be fixed (i.e., the $2m$ sets of coins for the weighings must be specified in advance) and must be able to uniquely identify the bag containing the fake coins.

Having reached this point, zzq finally remembered that he did not specify the number of bags of coins, so he wants you to output the maximum number of bags of coins that can be resolved, modulo 998244353. You do not need to output the weighing plan itself.

Input

The first line contains a positive integer $T$, representing the number of test cases. The next $T$ lines each contain two integers $m$ and $k$, representing a test case.

Output

Output $T$ lines, each representing the maximum number of bags of coins that can be distinguished for that test case, modulo 998244353.

Examples

Input 1

4
1 1
2 1
2 2
23 45

Output 1

3
9
17
648619844

For the first test case, we can weigh the first two coins; if the weights are different, the heavier one is the fake coin, otherwise the remaining one is the fake coin.

Regarding the fourth test case, I have a marvelous explanation, but the margin here is too small to contain it.

Note

For all data, $1 \leq m, k \leq 10^{5}, T \leq 10$.

• Subtask 1 (20 pts): $k=1$.
• Subtask 2 (20 pts): $m, k \leq 3$.
• Subtask 3 (30 pts): $m, k \leq 100$.
• Subtask 4 (30 pts): No special restrictions.