55pts求助

#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+7;
long long t,n;
/*
inline long long read(){
	long long res=0;
	char c;
	c=getchar();
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9'){
		res=res*10+c-'0';
		c=getchar();
	}
	return res;
}
*/
const int maxn=1e8+7;
int vis[maxn],prime[maxn],cnt;
void ol(int x){
	for(int i=2;i<=x;i++){
		if(vis[i]==0){
			prime[++cnt]=i;
		}
		for(int j=1;j<=cnt&&i*prime[j]<=x;j++){
			vis[i*prime[j]]=1;
			if(i%prime[j]==0)break;
		}
	}
}
long long ksm(long long a,long long p){
	long long f=1;
	a%=mod;
	while(p){
		if(p%2==1){
			f*=a;
			f%=mod;
		}
		a*=a;
		a%=mod;
		p/=2;
	}
	return f;
}
int main(){
	int x=1e6+3;
	ol(x);
	scanf("%lld",&t);
	while(t--){
		scanf("%lld",&n);
		long long k=n,ans=1;
		for(int i=1;i<=cnt;i++){
			if(k<=1)break;
			long long sum=0;
			while(k%prime[i]==0){
				sum++;
				k/=prime[i];
			}
			if(sum%2==1)sum--;
			ans=ans*ksm(prime[i],sum/2);
		}
		n%=mod;
		long long res=(n*n)%mod+ans%mod;
		cout<<res%mod<<endl;
	}
	return 0;
}