E. GCD and LCM in Perfect Sync
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Given $$$a_1$$$ and $$$n$$$, find the number of sequences of positive integers $$$a_2, a_3, \dots, a_n$$$ that satisfy the following condition:

$$$$$$ \frac{\operatorname{lcm}(a_1, a_2, \ldots, a_n)}{\gcd(a_1, a_2, \ldots, a_n)} = a_1 $$$$$$

Here, $$$\gcd(a_1, a_2, \dots, a_n)$$$ denotes the greatest common divisor, which is the largest positive integer that divides each number in the sequence, and $$$\operatorname{lcm}(a_1, a_2, \dots, a_n)$$$ denotes the least common multiple, which is the smallest positive integer that is divisible by each number in the sequence.

Since the answer can be large, output it modulo $$$998\,244\,353$$$. It can be proven that the answer is finite.

Input

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

The only line of each test case consists of two integers $$$a_1$$$ and $$$n$$$ ($$$2 \le a_1,n \le 10^9$$$).

Output

For each test case, output the number of sequences satisfying the condition above modulo $$$998\,244\,353$$$.

Example
Input
4
2 3
4 3
666 999
1000000000 1000000000
Output
6
12
15861573
208999360
Note

In the first test case, all the $$$6$$$ valid sequences are $$$[2,1,1],[2,1,2],$$$ $$$[2,2,1],[2,2,4],[2,4,2],$$$ and $$$[2,4,4]$$$.