### 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$$ ### output An integer representing your answer. ### sample input 1 10 2 ### sample output 2829 ### toturial \begin{aligned} &\sum_{i=1}^n\sum_{j=1}^n i*j*gcd(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} 我们可以对n分块了，前面可以min25筛 \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} 于是后面可以杜教筛 ### code

-----------------------本文结束感谢您的阅读-----------------------