在一个著名的 MOBA 游戏中，$n$ 个英雄排成一排。然而，其中一些可能是幻象。

观察者记录了每一对 $\ell$ 和 $r$ ($1 \le \ell \le r \le n$) 范围内（包含 $\ell$ 到 $r$）真实英雄的数量的奇偶性。她的 $\frac{n(n+1)}{2}$ 条记录显示，共有 $k$ 个区间包含奇数个真实英雄。请问有多少种可能的英雄排列方式？答案可能很大，请输出其对 $998\,244\,353$ 取模的结果。

如果两种排列中，从左往右数第 $i$ 个英雄在一种排列中是真实的，而在另一种排列中是幻象，则认为这两种排列不同。

输入格式

第一行包含一个整数 $t$：测试用例的数量 ($1 \le t \le 10^5$)。

接下来 $t$ 行，每行包含两个整数：$n$ 和 $k$ ($1 \le n \le 10^5$; $0 \le k \le n(n + 1)/2$)。

输出格式

输出可能的英雄排列数量，对 $998\,244\,353$ 取模。

样例

样例输入 1

1
5 9

样例输出 1

10

样例输入 2

4
3 4
6 12
6 11
12 30

样例输出 2

3
35
0
286