Consider all numbers from 1 to ‘N’, your task is to find the sum of gcd of all pairs (i, j) such that 1 <= i < j <= N.

For example for N = 3, all pairs are { (1, 2), (1, 3), (2, 3) }.

Note :

Gcd of two numbers (X, Y) is defined as the largest integer that divides both ‘X’ and ‘Y’. 

Input Format :

The first line contains an integer 'T' which denotes the number of test cases to be run. The 'T' test cases follow.

The first line of each test case contains an integer ‘N’ representing the given integer.

Output Format :

For each test case, print an integer representing the sum of gcd of all pairs of numbers from 1 to ‘N’.

The output of each test case will be printed in a separate line.

Note :

You do not need to input or print anything, and it has already been taken care of. Just implement the given function.

Constraints :

1 <= 'T' <= 5
1 <= 'N' <= 5000

Time Limit: 1sec