All Tracks Problem

Little Stuart and His Teacher
/

Algorithms, Mathematics

Problem
Editorial
Analytics

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.

Time Limit: 2.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

This Problem was Asked in

Initializing Code Editor...
Notifications
View All Notifications

?