Problem Description

One day, Touma Kazusa encountered a easy math problem. Given $n$ and $k$, she need to calculate the following sum modulo $1e9 + 7$.
$\sum_{i=1}^{n}\sum_{j=1}^{n}gcd(i,j)^klcm(i, j)[gcd(i,j)\in 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 \leq n \leq 1e10$
$1 \leq k \leq 100$

Output

An integer representing your answer.

1
10 2

2829