Credit

This problem is a partially modified version of an original idea provided by kobaryu325.

Problem Statement

In this problem, an array whose elements are each $0$ or $1$ is called a 01 array.

You are given positive integers $N,K$. Find the number of 01 arrays $X=(X_1,X_2,\dots , X_{2^N-1})$ of length $2^N -1$ satisfying the following condition.

• Consider an array $a$ of length $N$, initially $a_1 = 1,a_i = -1\ (2\le i\le N)$. After performing the following operations $0$ or more times, the number of distinct possible values of $a_N$ is exactly $K$.
  • Choose one $x$ such that $a_x \neq -1$ , $X_{a_x} = 1$ , $X_{2a_x} = 1$, and replace $a_{x+1}$ with $2a_x$.
  • Choose one $x$ such that $a_x \neq -1$ , $X_{a_x} = 1$ , $X_{2a_x+1} = 1$, and replace $a_{x+1}$ with $2a_x+1$.

Since the answer can be extremely large, find the answer modulo $998244353$.

Solve each of the $T$ test cases.

Input

$T$
$\mathrm{case}_1$
$\mathrm{case}_2$
$\vdots$
$\mathrm{case}_T$

Each test case is given in the following format.

$N\ K$

Constraints

• $1\le T\le 2\times 10^5$
• $2\le N \le 2\times 10^5$
• $1\le K \le $ $10$
• $N,K$ are integers.

Output

Output $T$ lines. On the $i$-th line, output the answer for the $i$-th test case modulo $998244353$.

Sample

2
2 2
100 10

2
95769305