题目描述

Iroha 买回来了一个汉诺塔玩具。这个玩具有从左到右三根柱子，最左边的柱子上有 $n$ 个圆盘，从上到下编号分别为 $1,2,\ldots,n$。

但是 Kaguya 嫌汉诺塔太无聊了，她把所有的圆盘全部取了下来，然后决定按照 $1,2,\ldots,n$ 的顺序，等概率地随机将圆盘放在三根柱子中某一根的最顶上。

例如：当 $n=5$ 时，$\boxed{\begin{array}c3\\2\end{array}}~\boxed{\begin{array}c5\\1\end{array}}~\boxed{\begin{array}c4\end{array}}$ 是一种合法的摆放方案，$\boxed{\begin{array}c5\\4\\2\\1\end{array}}~\boxed{\begin{array}c\end{array}}~\boxed{\begin{array}c3\end{array}}$ 也是合法的摆放方案，但是 $\boxed{\color{red}{\begin{array}c1\\2\end{array}}}~\boxed{\begin{array}c4\\3\end{array}}~\boxed{\begin{array}c5\end{array}}$ 不是合法的摆放方案。

Kaguya 想知道，她摆放好所有的 $n$ 个圆盘后，左边两个柱子最顶上的圆盘的编号之和等于 $k$ 的概率是多少。如果某个柱子是空的，那么我们认为最顶上的圆盘编号为 $0$。

例如：在上面的三个例子中，左边两个柱子最顶上的编号之和分别是 $8,5,5$（虽然第三种方案并不合法）。

如果最终的概率是 $\frac pq$，那么请输出 $(p \cdot q^{-1}) \bmod 998244353$，其中 $q^{-1}$ 为 $q$ 在模 $998244353$ 意义下的乘法逆元。

输入格式

第一行一个正整数 $T$，代表数据组数。接下来 $T$ 组数据，每组数据一行两个正整数 $n,k$。

输出格式

对于每组数据，输出一行一个整数，代表答案对 $998244353$ 取模的结果。

2
2 3
5 4

887328314
180752064

数据范围

• 对于 $30\%$ 的数据，$T \le 10$，$n \le 15$；
• 对于另外 $30\%$ 的数据，$k \le 500$；
• 对于 $100\%$ 的数据，$1 \le T \le 10^4$，$2 \le n \le 10^7$，$3 \le k \le 2n$。