Problem Description

Z is learning GCD theory and he finds a difficult problem:

$$
\sum_{i=1}^{n}\sum_{j=1}^{n}[\gcd(2^i-1,2^j-1)]^K
$$

He doesn't know how to solve it, but he knows it's easy for you. Please help him.

Since the answer can be very large, you only need to print the answer $\text{mod}\ 998244353$.

Input

The first line contains one integer $T\ (1\le T\le 12)$ which represents the number of test cases.

For each test case: One line contains two integers $n\ (1\le n\le 10^9)$ and $K\ (0\le K\le 10)$.

Output

For each test case: Print one line containing one integer which represents the answer.

3
3 1
3 2
3 3

17
65
377