GCD?LCM!
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:
Submit