GCD problem
/

Greatest common divisor, Mathematics, Medium-Hard, Mobius Inversion, Number Theory

Problem
Editorial
Analytics

For each set of four integers given $(i,j ,k,l)$ where $1\leq i < j <k <l \leq N$. You are required to compute the following:

$\displaystyle\sum_{i=1}^{N} \displaystyle\sum_{j=i+1}^{N}\displaystyle\sum_{k=j+1}^{N} \displaystyle\sum_{l=k+1}^{N} gcd(i,j,k,l) ^{4}$

Input format

• First line: $T$ that denotes the number of test cases
• Next $T$ lines: A integer $N$

Output format

Print the answer for each test case $Mod \,\,\,10^9+7$ in a new line.

Constraints
$1 \leq T \leq 10 \\ 1 \leq N \leq 10^5$

SAMPLE INPUT
2
4
5

SAMPLE OUTPUT
1
5

Explanation

For First Test case N=4 :
(1,2,3,4) :   gcd(1,2,3,4)4 = 1
Total sum = 1

For Second Test Case N=5 :
(1,2,3,4) :   gcd(1,2,3,4)4 = 1
(1,2,3,5) :   gcd(1,2,3,5)4 = 1
(1,2,4,5) :   gcd(1,2,4,5)4 = 1
(1,3,4,5) :   gcd(1,3,4,5)4 = 1
(2,3,4,5) :   gcd(2,3,4,5)4 = 1
Total sum = 1+1+1+1+1 = 5

Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB