GCD?LCM!

Problem Description

First we define: (1) $lcm(a,b)$, the least common multiple of two integers $a$ and $b$, is the smallest positive integer that is divisible by both $a$ and $b$. for example, $lcm(2,3)=6$ and $lcm(4,6)=12$. (2) $gcd(a,b)$, the greatest common divisor of two integers $a$ and $b$, is the largest positive integer that divides both $a$ and $b$ without a remainder, $gcd(2,3)=1$ and $gcd(4,6)=2$. (3) $[exp]$, $exp$ is a logical expression, if the result of $exp$ is $true$, then $[exp]=1$, else $[exp]=0$. for example, $[1+2\geq 3]=1$ and $[1+2\geq 4]=0$. Now Stilwell wants to calculate such a problem:

$$F(n)=\sum_{i=1}^n\sum_{j=1}^n~[~lcm(i,j)+gcd(i,j)\geq n~] \\ S(n)=\sum_{i=1}^nF(i)$$

Find $S(n)~mod~258280327$.

Input

The first line of the input contains a single number $T$, the number of test cases. Next $T$ lines, each line contains a positive integer $n$. $T\leq 10^5$, $n\leq 10^6$.

Output

$T$ lines, find $S(n)~mod~258280327$.

Sample Input

8
1
2
3
4
10
100
233
11037

Sample Output

1
5
13
26
289
296582
3928449
213582482

Author

SXYZ

Source

2015 Multi-University Training Contest 8