### name

Easy Math Problem

### descirption

One day, Touma Kazusa encountered a easy math problem. Given n and k, she need to calculate the following sum modulo $1e9+7$.
$$∑_{i=1}^n∑^n_{j=1}gcd(i,j)^klcm(i,j)[gcd(i,j)∈prime]%(1e9+7)$$
However, as a poor student, Kazusa obviously did not, so Touma Kazusa went to ask Kitahara Haruki. But Kitahara Haruki is too busy, in order to prove that he is a skilled man, so he threw this problem to you. Can you answer this easy math problem quickly?

### input

There are multiple test cases.$（T=5）$ The first line of the input contains an integer$T$, indicating the number of test cases. For each test case:
There are only two positive integers n and k which are separated by spaces.
$1≤n≤1e10$
$1≤k≤100$

1
10 2

2829

### toturial

\begin{aligned} &\sum_{i=1}^n\sum_{j=1}^n ijgcd(i,j)^{k-1} gcd is prime \=&\sum_{d\in prime} \sum_{i=1}^n\sum_{j=1}^nijd^{k-1}[gcd(i,j)=d] \=&\sum_{d\in prime} \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}ijd^{k+1}[gcd(i,j)=1] \=&\sum_{d\in prime}d^{k+1} \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}ij[gcd(i,j)=1] \=&\sum_{d\in prime}d^{k+1} \sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}j^2\phi(j) \end{aligned}

\begin{aligned}f(j)=j^2\phi(j)\end{aligned}
\begin{aligned}g(j)=j^2\end{aligned}
\begin{aligned}f\ast g(j)=\sum_{i|j}i^2\phi(i)(\frac{j}{i})^2=j^2\sum_{i|j}\phi(i)=j^2(\phi\ast 1)(j)=j^3\end{aligned}