#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn=5000001,mxn=maxn-1;
const LL MOD=1000000007;

LL a[maxn],s[maxn];
LL sum[maxn];
LL cal(LL a,LL b) {
	return (a+b)*(b-a+1)/2%MOD;
}
int main() {
	a[1]=1; a[2]=2; a[3]=2; int po=3;
	for (int i=3;po<mxn;i++) {
		for (int j=1;j<=a[i];j++) {
			if (po==mxn) break;
			a[++po]=i;
		}
	}
	for (int i=1;i<=po;i++)
		s[i]=s[i-1]+a[i];
	for (int i=1;i<=po;i++)
		sum[i]=(sum[i-1]+cal(s[i-1]+1,s[i])*i)%MOD;

	int T; scanf("%d",&T);
	for (LL n;T--;) {
		scanf("%lld",&n);
		LL i=upper_bound(s+1,s+1+po,n)-s-1;
		printf("%lld\n",(sum[i]+cal(s[i]+1,n)*(i+1))%MOD);
	}
    return 0;
}

/*
	Golomb's sequence
*/