F. Mandatory XOR Problem
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two integers $$$N$$$ and $$$S$$$. Consider all possible arrays $$$[a_1, a_2, \dots, a_n]$$$ of $$$N$$$ non-negative integers such that $$$a_1 + a_2 + \dots + a_n = S$$$.

For each such array, compute the bitwise XOR of all its elements, i.e., $$$a_1 \oplus a_2 \oplus \dots \oplus a_n$$$. Find the sum of these values over all possible arrays.

Since the answer can be very large, output it modulo $$$998244353$$$.

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 5 \cdot 10^4$$$) — the number of test cases. The description of the test cases follows.

Each test case consists of a single line containing two integers $$$N$$$ and $$$S$$$ ($$$1 \le N \le 5 \cdot 10^4$$$, $$$0 \le S \le 10^9$$$) — the length of the array and the required sum of elements.

It is guaranteed that the sum of $$$N$$$ over all test cases doesn't exceed $$$5 \cdot 10^4$$$.

Output

For each test case, output a single integer — the sum of XOR values over all valid arrays, modulo $$$998244353$$$.

Example
Input
3
1 5
2 2
2 3
Output
5
4
12
Note

In the first test case, the only valid array is $$$[5]$$$, and its XOR is $$$5$$$.

In the second test case, the valid arrays are $$$[0, 2]$$$, $$$[1, 1]$$$, and $$$[2, 0]$$$, with XOR values $$$2$$$, $$$0$$$, and $$$2$$$ respectively. The sum is $$$2 + 0 + 2 = 4$$$.

In the third test case, the valid arrays are $$$[0, 3]$$$, $$$[1, 2]$$$, $$$[2, 1]$$$, and $$$[3, 0]$$$, with XOR values $$$3$$$, $$$3$$$, $$$3$$$, and $$$3$$$ respectively. The sum is $$$3 + 3 + 3 + 3 = 12$$$.