题目描述
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$.
$$
\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$.
输入
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)$.
For each test case: One line contains two integers $n\ (1\le n\le 10^9)$ and $K\ (0\le K\le 10)$.
输出
For each test case: Print one line containing one integer which represents the answer.
样例输入 Copy
3
3 1
3 2
3 3
样例输出 Copy
17
65
377