Kancha likes calculating gcf very much !! Where gcf(x,y) is the greatest common factor of x and y.

He wants to calculate the sum of GCF's of all possible pairs in an array, where array of size N consists of numbers from 1 to N.

Input:
Input contains an integer t, which is the number of test cases, then t lines follow where each line contains an integer N, where N is the size of array.

Output:
Output the sum of GCD of all numbers taken pairwise.

Constraints:
0<t ≤ 10
1 ≤ N ≤ 400000

SAMPLE INPUT
1
3

SAMPLE OUTPUT
3

Explanation

gcd(1,2) = 1
gcd(1,3) = 1
gcd(2,3) = 1
total = 3

见题面

见题面