Log in
SOLVE
LATER
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.
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.
![](http://www.facebook.com/sharer.php?s=100&p[url]=https://www.hackerearth.com/problem/algorithm/little-stuart-and-his-teacher-20/&p[images][0]=https://static-fastly.hackerearth.com/static/hackerearth/images/logo/HE_cover.jpg&p[title]=Get your %23programming basics right! Solve this problem and see how good you are!"){kind=link}