little-stuart-and-his-teacher-20

Little Stuart is a smart guy, and he loves mathematics. Today his math teacher taught his class about common factors.  After finishing the class his teacher asked them a question: For a given number  "N" calculate the number of unordered pairs (A,B) which have at least one common factor where  1 ≤ A < B ≤ N .

Note: 1 is not considered as common factor.

Input :
First line contain the number of test cases "T"
Next  "T" lines  contain a number  "N"

Input Constraints:

1 ≤ T ≤ 100000

1 ≤ N ≤ 1000000

Output:
For each case print total number of pairs.

SAMPLE INPUT
3
1
2
5

SAMPLE OUTPUT
0
0
1

Explanation

For testcase - 3 ,   

N = 5  

Some possible pairs = [(1, 2), (2, 3), (2, 4), (3, 4), (4, 5)]   

The only pair which has common factor is (2, 4). So the answer is 1 for N = 5.   

Note: 1 is not considered as common factor.

Source: hackerearth | Difficulty: MEDIUM
Tags: Mathematics


Solutions: