F. Ebb and Flow
time limit per test
2 s
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given two non-negative integers $$$n$$$ and $$$m$$$.

An array of non-negative integers $$$a_1, a_2, \ldots, a_n$$$ is good if for every index $$$i$$$ ($$$1 \le i \le n$$$), the bitwise AND of the first $$$i$$$ elements equals the bitwise OR of the last $$$n - i + 1$$$ elements. Formally, the array is good if $$$$$$a_1 \mathbin{\&} a_2 \mathbin{\&} \cdots \mathbin{\&} a_i = a_i \mathbin{|} a_{i+1} \mathbin{|} \cdots \mathbin{|} a_n$$$$$$ holds for every $$$1 \le i \le n$$$.

Count the number of good arrays $$$a_1, a_2, \ldots, a_n$$$ such that $$$0 \le a_i \le m$$$ holds for every index $$$i$$$. Since the answer can be large, output it modulo $$$998244353$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

The only line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 10^{18}$$$, $$$0 \le m \le 10^{18}$$$).

Output

For each test case, output a single integer — the number of good arrays modulo $$$998244353$$$.

Example
Input
3
2 2
3 4
5 2
Output
5
19
11
Note

In the first test case, the good arrays are $$$[0, 0], [1, 0], [1, 1], [2, 0], [2, 2]$$$. For example, $$$[2, 0]$$$ is good because

  • for $$$i = 1$$$, $$$a_1 = 2$$$ equals $$$a_1 \mathbin{|} a_2 = 2$$$,
  • for $$$i = 2$$$, $$$a_1 \mathbin{\&} a_2 = 0$$$ equals $$$a_2 = 0$$$.