## 【杜教筛】HUD-6706 huntian oy

### 传送门

f=i\varphi(i)=id\varphi(i)
g=id
f*g(n)=\sum\limits_{i|n}\varphi(i)i\frac{n}{i}=n\sum\limits_{i|n}\varphi(i)

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e6 + 233;
typedef long long ll;
const ll mod = 1e9 + 7;
ll inv2, inv6;
bool st[maxn];
int primes[maxn], cnt;
ll phi[maxn];
unordered_map<int, ll> up;
ll ksm(ll n, ll k)
{
ll res = 1;
while(k)
{
if(k & 1) res = res * n % mod;
n = n * n % mod;
k >>= 1;
}
return res;
}
void get_primes(int n)
{
// mu[1] = phi[1] = 1;
phi[1] = 1;
for(int i = 2; i <= n; i++) {
if(!st[i]) {
primes[cnt++] = i;
phi[i] = i - 1;
// mu[i] = -1;
}
for(int j = 0; j < cnt && i * primes[j] <= n; j++) {
st[i * primes[j]] = 1;
if(i % primes[j] == 0) {
phi[i * primes[j]] = phi[i] * primes[j];
// mu[i * primes[j]] = 0;
break;
}else {
phi[i * primes[j]] = phi[i] * (primes[j] - 1);
// mu[i * primes[j]] = -mu[i];
}
}
}
for(ll i = 1; i <= n; i++) phi[i] = (phi[i - 1] + phi[i] * i % mod) % mod;
//phi[1] = 0;
}
ll Get_f_g(ll n)
{
return 1LL * n * (n + 1) % mod * (n * 2 + 1) % mod * inv6 % mod;
}
ll Get_g(ll n)
{
return n * (n + 1) % mod * inv2 % mod;
}
ll Getsum(ll n)
{
if(n < 5000000) return phi[n];
if(up[n]) return up[n];
ll ans = Get_f_g(n);
for(ll l = 2, r; l <= n; l = r + 1)
{
r = n / (n / l);
ans -= (Get_g(r) - Get_g(l - 1)) * Getsum(n / l) % mod;
ans %= mod;
}
return up[n] = ans;
}
int main()
{
inv2 = ksm(2, mod - 2);
inv6 = ksm(6, mod - 2);
int T; cin >> T;
get_primes(5e6 + 10);
while(T--)
{
ll n, a, b;
scanf("%lld%lld%lld", &n, &a, &b);
ll ans = 0;
ans = (Getsum(n) - 1) * inv2 % mod;
printf("%lld\n", (ans + mod) % mod);
}
}