给定两个整数 $k$ 和 $p$。计算 $$\sum_{n=k}^{\infty} \frac{\binom{n}{k}^p}{2^n}$$ 其中 $\binom{n}{k}$ 表示二项式系数，等于 $\frac{n!}{k! \cdot (n-k)!}$。 题目保证结果可以表示为 $\frac{r}{q}$ 的形式，其中 $r$ 和 $q$ 是互质的正整数且 $q \neq 0$。求 $r \cdot q^{-1} \pmod{998\,244\,353}$。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 2112$)，表示测试用例的数量。接下来是各测试用例。 每个测试用例由一行描述，包含两个整数 $k$ 和 $p$ ($k, p \ge 1; p \cdot k \le 10^6$)。 所有测试用例中 $p \cdot k$ 的总和不超过 $10^6$。

输出格式

对于每个测试用例，输出一行，包含整数 $r \cdot q^{-1} \pmod{998\,244\,353}$，即计算结果。

样例

样例输入 1

3
2 3
1 10
9 6

样例输出 1

818
204495126
16726290