#include <cstdio>#include <cstring>#include <iostream>using namespace std;typedef long long LL;const LL Mod = 1000000007;#define bit(k) (1<<(k))const int N = 10005;int cs, n, r, ans;int q[11111];bool vis[N];int que[11111], cnt;void Primetable(){ memset(vis, 0, sizeof(vis)); cnt = 0; for(int i=2; i < N; ++i) if(!vis[i]){ que[cnt++] = i; for(int j=i+i;j<N;j+=i) vis[j] = 1; }}inline int mul(int a, int b){ return (LL)a*b%Mod;}inline int add(int a, int b){ return ((LL)a+b+Mod)%Mod;}int quickpow(int a, int b){ int ret = 1, delta = a; while(b){ if(b&1) ret = mul(ret, delta); delta = mul(delta, delta); b>>=1; } return ret;}int calc(int u, int flag){ int p = n/u, u1, p1, p2; if(flag){ u1 = mul(u,u); u1 = mul(u1,u1); } else u1 = 1; p1 = mul(p, p+1); p1 = mul(p1, 2*p+1); p2 = mul(3,mul(p,p)); p2 = add(add(p2, mul(3,p)),-1); p1 = mul(p1, p2); p1 = mul(p1, cs); return mul(u1, p1);}void dfs(int u, int mark, int plus){ int x = __builtin_popcount(mark); if(u==r){ if(x&1) ans = add(ans,calc(plus,1));else ans = add(ans,-calc(plus,1)); return; } dfs(u+1,mark,plus); dfs(u+1,mark|bit(u),plus*q[u]);}int main(){ Primetable(); cs = quickpow(30, Mod-2); int tt, nn, last, i; scanf("%d",&tt); while(tt--){ scanf("%d",&n); nn = n; r = 0; for(i=0;i<cnt;++i) if(nn%que[i]==0){ q[r++] = que[i]; while(nn%que[i]==0) nn/=que[i]; } if(nn>1) q[r++] = nn; ans = 0; dfs(0, 0, 1); ans = add(ans, 1); ans = add(calc(n,0),-ans); printf("%dn", ans); } return 0;}
