问题1226--简单的数学题

1226: 简单的数学题

[命题人 : ]
时间限制 : 2.000 sec  内存限制 : 512 MB

题目描述

给定一个正整数n,对于所有\(1\le j\le i\le n,\gcd(i,j)=1\)的整数对\( (i,j) \),求\(  \lceil  \frac{i}{j} \rceil \) 的和,即:

\( \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{i} \lceil \frac{i}{j} \rceil [\gcd(i,j)=1]  \) 

其中,\(\gcd(i,j)\)表示\(i\)与\(j\)的最大公因数;\(  \lceil  x \rceil \)表示\(x\)向上取整的值;\(  [x] \)为一个变量,当x为真时值为1,否则为0.
答案对\(10^9 + 7\)取模

输入

第一行一个正整数T(1<=T<=500),表示数据组数
接下去T行,每行一个正整数n(1<=n<=1e9)
保证最多只有5组数据大于1e6。

输出

T行,第i行一个整数表示第i组的答案

样例输入 Copy

1
3

样例输出 Copy

8