×

计蒜客

  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