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$.

8
1
2
3
4
10
100
233
11037

1
5
13
26
289
296582
3928449
213582482

Author

SXYZ