[cf]C. Strange Function（lcm）

表示不能被i整除的、最小的正整数，给出一个n，让我们求出 。()

    考虑到n的范围很大，暴力会超时。

    观察一下f(i)，假设f(i)=j。我们可以观察一下i的所有因子的最小公倍数，，因为(1, 2, .., j-1)都是i的因子，它们的最小公倍数最大也只能为i。当i等于n时，j也不会很大(cf里的题解说小于100)，因为lcm(1, 2, ..., j-1) 的增长速度很快。然后我们能否通过列举j来计算答案呢，实际上是可以的。

     就是1~n中所有不能被j整除的数的数量，也就是所有f(x)值为j的数的数量。要知道1~n中有几个数可以被x整除，可以用来计算。

 表示1~n中被lcm(1, 2, ..., j-1)整除的数的数量，1~n中被lcm(1, 2, ..., j-1)

整除的数的数量 = 1~n中能被lcm(1, 2, ..., j)整除的数量 + 1~n中不能被lcm(1, 2, ..., j)整除的数量。

    我们可以将1~n中的所有数(假设为)分为 这样的组

别，那么我们就可以用 f(x)值为1的数的数量+f(x)值为2的数的数量+...来计算答案，

也就是  1}^{} j*(left lfloor n/lcm(1, 2, ..., j-1) right rfloor - left lfloor n/lcm(1, 2, ..., j) right rfloor)" src="https://latex.codecogs.com/gif.latex?%5Csum_%7Bj%3E1%7D%5E%7B%7D%20j*%28%5Cleft%20%5Clfloor%20n/lcm%281%2C%202%2C%20...%2C%20j-1%29%20%5Cright%20%5Crfloor%20-%20%5Cleft%20%5Clfloor%20n/lcm%281%2C%202%2C%20...%2C%20j%29%20%5Cright%20%5Crfloor%29" />  ，经过化简可得，

  。  

#include
using namespace std;
#define ll long long
const int mod=1e9+7;

ll gcd(ll a, ll b)
{
	return b? gcd(b, a%b): a;
}

ll lcm(ll a, ll b)
{
	return a/gcd(a, b)*b;
}

int main(){
	int t;
	cin>>t;
	while(t--)
	{
		ll n;
		cin>>n;
		ll G=1;
		ll ans=0;
		for(int i=1; G<=n; i++)
		{
			G=lcm(G, i);
			//cout<n) break;
			ans=(ans+n/G)%mod;
		}
		cout<<(ans+n)%mod<