#include
#define int long long
#define MAXN 1000005
using namespace std;
const int p=1e9+7;
int my_pow(int a,int b)
{
int res=1;
while(b)
{
if(b&1)
{
res=(res*a)%p;
}
a=(a*a)%p;
b>>=1;
}
return res;
}
int phi(int x)
{
int res=x,yx=x;
for(int i=2;i*i<=yx;i++)
{
if(x%i) continue;
res-=res/i;
while(!(x%i)) x=x/i;
}
if(x>1) res-=res/x;
return res%p;
}
int T;
int n,tot;
int F(int x)
{
return (my_pow(n,x)*phi(n/x)%p)%p;
}
signed main()
{
//定义群:集合+计算符号
//封闭性:无论怎么计算都在群内
//结合律:(A*B)*C=A*(B*C)
//单位元:e在群内,e*A=A
//逆元:A*A'=e
//考虑什么是单位元,一定是一个元素乘另一个元素是本身
//子群:
//元素全部属于G,也满足群的性质
//陪集:
//G是一个群,H是G的子群
//且有g包含于G
//如果a*h=aH那么a是H在G里面的左陪集
//自然也有右陪集
//下面讨论右陪集
//陪集的性质:
//任取g属于G
//|H|=|Hg|
//肯定不一样
//g属于Hg
//有单位元显然
//Hg=H,g属于H
//显然
//Ha=Hb
//Ha*b'=H
//a*b'属于H
//陪集不是完全不同就是完全一样
//如果有相同部分肯定能搞出来,因为封闭性
//全体右陪集的并是G
//也很显然了
//拉格朗日定理
//有限群G,和有限群H
//若H是G的子群
//那么有|H|整除|G|
//H的阶整除G的阶
//|H|*|G:H|=|G|
//也显然,每个不一样,而且对应搞出来是全集
//置换:
//第一行是原来的数
//第二行是新的位置的是上一层哪一个位置
//不同置换n!个
//置换群
//(G,*)排列集合+置换=置换群
//有封闭性,有全部排列
//逆元,单位元必然存在
//群作用,分为左群作用和右群作用
//传入二元函数f(e,k)=k(e是单位元)
//f(g,f(s,k))=f(g*s,k) k是M的元素
//理解一下就是先给里面函数一下的结果作用于和两个提前作用一样
//G作用于M
//轨道-稳定子定理
//考虑一个作用于X上的群
//X的一个元素x的轨道则是x变成X里的元素
//可以转移到元素的集合
//G(x)就是轨道,g(x)=f(g,x)
//稳定自G(x)={g|g属于G,g(x)=x}
//就是怎么变都是自己
//就是所有满足g能让x变成自己的元素的集合
//给定一个2*2的矩阵
//每个点都可以黑白染色
//所有的元素构成的矩阵集合M
//当一个元素经过置换可以得到
//那么他们属于一个等价类
//轨道大小于稳定子大小乘积为4,刚好是G的大小
//集合是那几个
//群是旋转,稳定子是所有的的群里的元素
//得到结论
//稳定子大小乘轨道大小就是一个群大小
//这就是轨道-稳定自定理
//|Gx|*|G(x)|=|G|
//Gx是G的子群必然
//e属于Gx的元素
//稳定子是群里的,轨道G(x)=f(x,k)
//当x作用任何k都不变,那就是稳定子
//Gx是所有g让g(x)=x的元素
//定理重新强调
//|Gx|*|G(x)|=|G|
//稳定子大小*轨道大小是总的集合大小
//继续
//Gx是G的子群显然
//Gx存在逆元
//感觉是群的话就有封闭性
//貌似也是,Gx不是稳定子吗,那么乘起来肯定也是稳定子了呗
//逆元的话也是必然有
//那么拉格朗日定理证明
//|Gx|*|G:Gx|=|G|
//感觉挺对的
//就是稳定子大小*不同陪集大小=全集
//Burnside定理
//定义一个置换群G
//定义作用于集合X
//就是那个运算f(g,x)
//x,y在作用下相等意味着
//f(g,x)=y
//那么x,y属于一个等价类
//就是能经过一些置换能互相到达
//那么不同等价类的数量是|X/G|=1/|G|(sum)Xg
//X是集合,G是置换群
//|X/G|是不同等价类的数量
//就是类似的吧全集分到好几个群里了
//Xg就是在g的作用下不动点的数量
//在g的作用下f(g,x)=x
//给出结论,等价类数量等于每一个g作用于X的不动点的算术平均值
//证明：
//由于每个元素仅属于一个轨道,并且内部互相到达
//陪集的性质可以得到
//|G:Gx|=|G|/|Gx|
//G的所有不同的轨道=总集合/稳定子
//枚举所有X
//那么又因为反了,所以
//|X/G|=(sum)Gx/G
//这个式子表示的是
//Gx那能让x不变的所有的置换
//那么这个式子的是所有的不动点的数目
//不同等价类的数量
//分两种,无非是每个置换的所有不动点加起来
//或者是每个不动点对应哪些g
//那个式子就可以表示|G:X|所有的不同等价类
//1/|G|*每个置换对应的不动点数量和
//这道题的答案无非是,等价类的种类
//M为{1->n}的所有排列表示的初始的换(集合)
//Ans=1/|G|*(sum)Mg
//就是每个置换的不动点的数量
//考虑每个置换的贡献是多少
//考虑每个置换的不动点的数量表示什么
//就是当前置换下还是本身的数量
//对于旋转k个而言,我们知道一个元素的不动点等价于存在
//不动点等价于存在长度为a的循环节,满足a|k
//那么a|n,貌似很显然的
//那么条件就是存在长度为gcd(k,n)的循环节
//那么就是1/n*i^gcd(i,n)
//那么polya是什么
//这道题也是求不动点
//那么貌似很显然的,转多少圈就是几个可操作点
//polya了
//1/|G|(sum)m^{cg}
cin>>T;
while(T--)
{
cin>>n;
for(int i=1;i*i<=n;i++)
{
if(n%i) continue;
tot+=F(i)%p;
tot%=p;
if(i*i!=n)
{
tot+=F(n/i)%p;
}
}
tot=tot*my_pow(n,p-2)%p;
printf("%d\n",tot%p);
tot=0;
}
}