As we have seen that Vaishnav was a smart kid and today he has grown up(but he is still childish) and he is in High school.

Today he was back from school and found that 4 pieces of Pizza was ordered- one for his father, one for this mother, and one for Vaishnavi and one for him. But Vaishnav was little late from school and when he came back he found that little Vaishnavi ate half of his PIZZA. And both of them started fighting. And as usual Vaishnav being the elder one got punished.

He was not in a mood to study today. Late at night he came to know that he has a Math problem to do and he is not in a mood to do. If he does not do the home-work he will be thrown out of the class the very next day. So he asks you for help.

He knows that you are the best person to do the home work as you are good in math. The question is like that given a number N we have to find the number of positive rational numbers which is less than 1 so that when it is expressed as P/Q it will be less than one and both P and Q will be less than or equal to N.

Input:

The first line contains T, the number of test cases. Followed by T lines each contain N.

Output:

Print the N lines for the output of each query.

Constraints :

   1<=T<=10000
   1<=N<=10000

Problem Setter : Bipin Baburaj

Problem Tester : Darshak Mehta