Fibonacci-th Fibonacci

問題文

数列 $F,A$ を

\begin{equation*} F_n= \begin{cases} n & \text{if $n \le 1$}\\ F_{n-1}+F_{n-2} & \text{otherwise} \end{cases} \end{equation*}

\begin{equation*} A_n= \begin{cases} N & \text{if $n=0$}\\ F_{A_{n-1}} & \text{otherwise} \end{cases} \end{equation*}

とするとき、 $A_K$ を $998244353$ で割った余りを求めてください。

$T$ 個のテストケースが与えられるので、それぞれについて答えてください。

入力は以下の形式で標準入力から与えられる。

T

\mathrm{case}_1

\mathrm{case}_2

\vdots

\mathrm{case}_T

各テストケース $\mathrm{case}_t ~ (1 \leq t \leq T)$ は以下の形式で与えられる。

N \quad K

$T$ 行出力せよ。 $t$ 行目には $t$ 番目のテストケースについての答えを出力せよ。

3
3 5
6 3
998244353 998244353

1
10946
838877215

一つ目のテストケースについて、

$n$	$0$	$1$	$2$	$3$	$4$	$5$	$6$
$F_n$	$0$	$1$	$1$	$2$	$3$	$5$	$8$
$A_n$	$3$	$2$	$1$	$1$	$1$	$1$	$1$

なので $A_5=1$ です。

二つ目のテストケースについて、 $A_0=6, A_1=8, A_2=21, A_3=10946$ です。