GCD Magic

Problem Description

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

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.

Sample Input

3
3 1
3 2
3 3

Sample Output

17
65
377

Source

2023“钉耙编程”中国大学生算法设计超级联赛（5）