リスペクト

本問題はkobaryu325氏によって提供された原案を一部改題したものです。

問題文

この問題では、各要素が $0$ か $1$ である配列を01配列と呼ぶものとします。

正整数 $N,K$ が与えられます。以下の条件を満たす長さ $2^N -1$ の01配列 $X=(X_1,X_2,\dots , X_{2^N-1})$ の個数を求めてください。

• はじめ $a_1 = 1,a_i = -1\ (2\le i\le N)$ である長さ $N$ の配列 $a$ に対して以下の操作を $0$ 回以上行ったあとの $a_N$ としてあり得る値はちょうど $K$ 種類である。
  • $a_x \neq -1$ , $X_{a_x} = 1$ , $X_{2a_x} = 1$ である $x$ を一つ選び、 $a_{x+1}$ を $2a_x$ に置き換える。
  • $a_x \neq -1$ , $X_{a_x} = 1$ , $X_{2a_x+1} = 1$ である $x$ を一つ選び、 $a_{x+1}$ を $2a_x+1$ に置き換える。

ただし、答えは極めて大きくなる可能性があるので、答えを $998244353$ で割ったあまりを求めてください。

$T$ 個のテストケースについて、それぞれ答えを求めてください。

入力

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

各テストケースは以下の形式で与えられます。

$N\ K$

制約

• $1\le T\le 2\times 10^5$
• $2\le N \le 2\times 10^5$
• $1\le K \le $ $10$
• $N,K$ は整数

出力

$T$ 行出力してください。$i$ 行目には、 $i$ 番目のテストケースについての答えを $998244353$ で割ったあまりを出力してください。

サンプル

2
2 2
100 10

2
95769305