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