Link to Russian translation of problem

You are given positive integer N. How many unordered pairs of integers from 1 to N are coprime?

Input
The first line contains one integer T denoting the number of test cases. The following T lines contain one number each - N and describe each test case.

Output
For each test case output one integer per line - answer for the question.

Constraints

• N <= 10⁷
• T <= 10