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