Given the positive integer , find the value of that is computed by the following code:
Totient or phi function, is an arithmetic function that counts the number of positive integers less than or equal to that are relatively prime to . That is, if is a positive integer, then is the number of such integers , for which .
The first line contains the number of test cases . It is followed by lines each containing a number .
For each line produce one line that contains the value of for the corresponding .