GCD?LCM!

Time Limit
1s
Memory Limit
131072KB
Judge Program
Standard
Ratio(Solve/Submit)
100.00%(6/6)
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≥3]=1 and [1+2≥4]=0.

Now Stilwell wants to calculate such a problem:

F(n)=∑i=1n∑j=1n [ lcm(i,j)+gcd(i,j)≥n ]S(n)=∑i=1nF(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≤105, n≤106.

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
Source:

2015 Multi-University Training Contest 8


Submit