bookface

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 1000001;
int N,nr,K,P[MAX_N][8];
long long FR[MAX_N];
bitset <MAX_N> viz;

inline unsigned long long pow(long long x,int pt)
{
    unsigned long long rez=1;
    for(;pt;pt>>=1)
        if(pt&1)
            rez*=x;
        x*=x;
    return rez;
}

int main()
{
    FR[1]=1;
    for(int i=2;i<MAX_N;++i)
    {
        if(viz[i]==0)
        {
            P[i][0]=1;
            P[i][1]=i;
            FR[i]=(1+i+1LL*i*i);
            for(int j=i+i;j<MAX_N;j+=i)
            {
                viz[j]=1;
                ++P[j][0];
                P[j][P[j][0]]=i;
            }
        }
    }
    for(int i=4;i<MAX_N;++i)
    {
        if(FR[i]==0)
        {
            int aux=i,p=P[aux][P[aux][0]],j=aux/p;
            if(j%p!=0)
                FR[i]=FR[j]*(1+p+1ULL*p*p);
            else
            {
                int k=0;
                unsigned long long p1=1;
                while(aux%p==0)
                    ++k,p1*=p,aux/=p;
                unsigned long long p2=1ULL*(pow(p,2*k+1)-1)/(p-1);
                FR[i]=FR[i/p1]*p2*1ULL;
            }
        }
    }
    ifstream f("bookface.in");
    f>>N;
    ofstream g("bookface.out");
    for(int i=1;i<=N;++i)
        f>>nr,g<<FR[nr]<<'\n';
    return 0;
}