×

# 计蒜客

1. 题库
2. K Sum
3. 问答
• 23.65%
• 262144K

Define function

$$\displaystyle f_n(k)=\sum_{l_1=1}^n \sum_{l_2=1}^n ... \sum_{l_k=1}^n (\gcd(l_1,l_2,...,l_k))^2$$.

Given $n(1 \le n \le 10^9),k(2 \le k \le {10}^{10^5})$, please calculate

$$\displaystyle \sum_{i=2}^k {f_n(i)}$$

modulo $10^9 + 7$.

### Input

There are multiple test cases, the first line contains an integer $T(1 \le T \le 10)$, denoting the number of test cases.

For the next $T$ lines, each line contains two integers $n(1 \le n \le 10^9)$ and $k(2 \le k \le 10^{10^5})$.

### Output

For each test case, print one line contains an integer, which is the value of $\sum_{i=2}^k {f_n(i)}$.

#### 样例输入

2
2 2
100 3

#### 样例输出

7
4331084

• main.c