今天现场赛模拟来着，D题做的很快，15分钟就出了，然后就一直死磕I题了，刚开始想到了要减去不互素的数，结果不知道容斥原理，只能赛后AC了。
大体思路就是，先算出1到n的四次方和，然后减去不互素的四次方和，然后计算这个就比较麻烦了，首先把n给素数分解，然后就运用容斥原理，各种减减加加，目的就是防止减掉重复的，比如2的倍数有2,4,6,8……，3的倍数有3,6,9……，然后2和3中都有6，所以这点就比较麻烦了。类似的还有含多个质因子的数。
然后我容斥是用dfs实现的，其中也有好多细节吧，比如计算四次方和公式里面，有个除以30，就不能用模了，但是，不用又会超，听别人说用逆元做的，我也不知道是啥，就用了个很土的方法做的。然后乘法的时候每次乘都要模一次，减法的时候还可能出现负数，也要处理一下，总之，各种模了。
/*
ID: sdj22251
PROG: subset
LANG: C++
*/
#include <iostream>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cctype>
#include <string>
#include <cstring>
#include <cmath>
#include <ctime>
#define LOCA
#define MAXN 1005
#define INF 100000000
#define eps 1e-7
using namespace std;
struct wwj
{int num;int cnt;
}node[200];
bool tag[120001];
long long p[110001], v[200];
int cnt, num;
long long n, m;
long long mod = 1000000007LL;
long long f(long long x)
{long long x1 = x;long long x2 = (x + 1);long long x3 = (2 * x + 1);long long x4 = (3 * x * x + (3 * x - 1));if(x1 % 2 == 0) x1 /= 2;else if(x2 % 2 == 0) x2 /= 2;else if(x3 % 2 == 0) x3 /= 2;else if(x4 % 2 == 0) x4 /= 2;if(x1 % 3 == 0) x1 /= 3;else if(x2 % 3 == 0) x2 /= 3;else if(x3 % 3 == 0) x3 /= 3;else if(x4 % 3 == 0) x4 /= 3;if(x1 % 5 == 0) x1 /= 5;else if(x2 % 5 == 0) x2 /= 5;else if(x3 % 5 == 0) x3 /= 5;else if(x4 % 5 == 0) x4 /= 5;x4 %= mod;return x1 * x2 % mod * x3 % mod * x4 % mod;
}
void get_prime()
{cnt = 0;for (int i = 2; i < 11000; i++){if (!tag[i])p[cnt++] = (long long)i;for (int j = 0; j < cnt && p[j] * i < 11000; j++){tag[i * p[j]] = 1;if (i % p[j] == 0)break;}}
}
long long sum;
void dfs(int x, int ct, int deep)
{if(ct >= deep ) return;v[ct] = node[x].num;if(ct == deep - 1){long long xx = v[0];for(int j = 1; j <= ct; j++)xx *= v[j];sum = (sum + f(m / xx) * xx % mod * xx % mod * xx % mod * xx % mod) % mod;return;}for(int i = x + 1; i < num; i++)dfs(i, ct + 1, deep);
}int main()
{
#ifdef LOCALfreopen("d:/data.in","r",stdin);freopen("d:/data.out","w",stdout);
#endifint t, i, j;get_prime();long long ans;cin >> t;while(t--){cin >> m;n = m;num = 0;for(i = 0; i < cnt && p[i] * p[i] <= n; i++){int tmp = 0;if(n % p[i] == 0){while(n % p[i] == 0){tmp++;n /= p[i];}node[num].num = p[i];node[num++].cnt = tmp;}}if(n != 1){node[num].num = n;node[num++].cnt = 1;}ans = f(m);for(i = 1; i <= num; i++){sum = 0;long long tmp;for(j = 0; j < num; j++)dfs(j, 0, i);tmp = sum;if(i % 2)ans = ((ans - tmp) % mod + mod) % mod; else ans = (ans + tmp) % mod;}if(m == 1) puts("0");elsecout << (ans + mod ) % mod << endl;}return 0;
}