Migrated from Lutece 2673 莉西娅之章 - 骑士团长的惩罚

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

「身为王者，其言行将左右万民之命」

「即使并非战时，也必须做好背负众人性命的觉悟」

「正因如此，王才必须要成为万民之父」

$\space$

$\space$ 莉西娅是诺瓦斯王室的王女。国王安排近卫骑士团团长法利亚斯来对王女进行教育与管理。不过，由于法利亚斯较为严苛的管理，莉西娅从小就对他感到害怕，到后来叛逆期时的不满，导致她在很多时候都会做出一些事情来故意惹法利亚斯生气。

一日，莉西娅王女像往常一样，扮作佣人并自己洗衣服，做些佣人应该做的事情。

这么做按她的理由，是为了体验人民的生活，对人民的一种关怀。不过很不幸，这件事被法利亚斯知道了，于是他仍然像往常一样对莉西娅进行教育惩罚。

法利亚斯安排自己的近卫骑士团排成一个 $n\times n$ 的方阵，第 $i$ 行第 $j$ 列的骑士手上拿着一个数字 $f(\gcd(i,j))$，其中 $f(n)=\sum\limits_{d|n}d\varphi(d)$，其中 $\varphi(n)=\sum\limits_{i=1}^{n}[\gcd(n,i)=1]$，即欧拉函数。

法利亚斯将这个方阵写成矩阵并交给莉西娅，给她的惩罚就是需要在晚上之前计算出这个矩阵的行列式。由于答案可能很大，她只需要求得答案对 $10^9+7$ 取模的结果。

Input

第一行一个正整数 $T$，表示有 $T$ 组数据。

接下来对于每一组数据输入一行一个正整数 $n$。

Output

对于每组数据输出一行一个整数表示答案。

Samples

3
1
2
3

1
2
12

Constraints

$1\le n,T \le 10^{6}$

Resources

2021 UESTC ICPC Training for Math and Geometry