Problem Statement

Define the set $I$ as the set containing each integer between $0$ and $N-1$, inclusive, exactly once.
Also, take arbitrary subsets $J_1 , J_2 , ... J_K $ of $I$.

Here, the beauty of the tuple of $K$ subsets $J_1 , J_2 , ... J_K $ is defined as the number of elements in their union. (For the precise definition of union, see here.)
Calculate the sum of the beauty over all ways to choose $J_1, J_2, ... J_K$.
Since the answer can be very large, find it modulo $998 244 353$.

$T$ test cases are given; answer each of them.

Input

$T$
$N_1\ K_1$
...
$N_T\ K_T$

All inputs are integers.
$1 \leq T \leq 100$
$1 \leq N \leq 10^9$
$1 \leq K \leq 10^9$

Output

Output $T$ lines. On the $i$-th line, output the $i$-th answer modulo $998 244 353$.
Print a newline at the end.

Sample

3
1 2
3 7
172894913 183245832

3
6242304
358532619