Background

SWW is a master of Number Theory. One day, she thought of a problem in her dream and she wants to challenge you.

She defines function f(n) as the number of different pairs $(x, y)$ that satisfies $x+y = n$ and $gcd(x, y) = 1$.

It’s simple to calculate $f(n)$ for any given $n$, so she defines another function $g(n)$, where

$$g(n) = ∑\limits_{d|n}f(⌊\frac{n}{d}⌋)$$

Now, SWW wants you to calculate the value of $F_k(n)$, where

$$F_k(n) = \begin{cases} n & , k = 0 \\ f(F_{k - 1}(n)) & , k > 0, k≡1(mod\;2) \\ g(F_{k - 1}(n)) & , k > 0, k≡0(mod\;2) \end{cases} $$

Input

There are multiple test cases.

The first line contains an integer $T (1 ≤ T ≤ 5)$, representing the number of test cases.

Each of the following T lines contains two integers $n$ and $k$, where $1 ≤ n$, $k ≤ 10^{12}$.

Output

For each test case, you need to output one integer in a single line, which represents $F_k(n)$ mod $(10^9 + 7)$.

Samples

3
15 2
233 3
23333333333 3

8
112
271986803