WHY MY TIME LIMIT IS EXCEEDING
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD=1000000007;
ll MAXN=4000001;
ll spf[4000002];
void sieve()
{
spf[1] = 1;
for (ll i=2; i<MAXN; i++)
// marking smallest prime factor for every
// number to be itself.
spf[i] = i;
// separately marking spf for every even
// number as 2
for (ll i=4; i<MAXN; i+=2)
spf[i] = 2;
for (ll i=3; i*i<MAXN; i++)
{
// checking if i is prime
if (spf[i] == i)
{
// marking SPF for all numbers divisible by i
for (ll j=i*i; j<MAXN; j+=i)
// marking spf[j] if it is not
// previously marked
if (spf[j]==j)
spf[j] = i;
}
}
}
ll solve(ll k){
ll x,y;
y=k;
ll ans=1;
while(y!=1){
ll i=spf[y];
if(y%i==0){
ll count=0;
x=y;
while(y%i==0){
y=y/i;
count++;
}
x=x/y;
ans*=((count+1)x)-(count(x/i));
}
}
return ans;
}
int main(){
ll t;
cin>>t;
sieve();
while(t--){
ll k;
cin>>k;
cout<<((solve(4*k+1)+4*k+1)/2)-1<<endl;
}
}