P21428 [HackerEarth] Given an integer N. Find eular toitent function of N. Eular toitent function of N is total number of positive integers less than N which are co-prime to N. Two numbers A and B are said t
普及-
题目描述

Given an integer N. Find eular toitent function of N. Eular toitent function of N is total number of positive integers less than N which are co-prime to N. Two numbers A and B are said to be co-prime if their greatest common divisor is 1. For eg 4 and 5 are co-prime to each other but 4 and 6 are not co-prime.

Input
First line contains T (number of test cases).
Next T lines contains integer N.
Constraints

1 ≤ T ≤ 100
2 ≤ N ≤ 10^6

SAMPLE INPUT
3
4
7
10

SAMPLE OUTPUT
2
6
4

输入格式

见题面

输出格式

见题面

样例输入
100 20520 58311 12672 12400 12168 80256 10404 14877 22620 24192 20300 4968 48735 76908 19800 75168 12600 22475 17204 40824 4080 4692 13728 10240 4212 53040 81900 15120 27945 20930 26928 15120 18144 43659 5580 84000 7200 26622 95256 11960 62400 25840 85374 23184 15312 10692 56644 11250 13680 3480 26334 12012 64800 14280 43008 30240 30240 30464 48960 6699 10920 88536 17710 90168 9728 13671 32340 20250 35112 9576 6496 19656 3465 49896 4200 37800 6426 12350 81432 29700 8316 14560 24360 24480 15750 26880 10752 38016 31620 9982 27000 7018 11571 81600 3672 13920 11284 14421 12960 57024
样例输出
896 2160 7776 864 3168 11520 3840 6048 6048 13056 11520 8640 6720 10752 14400 1536 8064 9600 8640 23040 8640 60632 6400 10560 17280 28224 4704 5520 19008 14080 4608 3360 7040 6400 4536 12960 1920 7920 16640 3840 20736 2016 5280 1024 33600 432 7040 12096 21504 8064 1440 4608 2560 2016 22680 23328 1536 9216 14400 23040 24192 4480 16632 6072 14784 48672 5184 1944 6000 12880 19136 44160 10800 4320 2592 3888 17280 12960 15360 20800 13248 26496 12800 2080 1040 1440 8640 11520 1536 3072 11520 4992 42336 3072 4608 37440 29568 5440 5880 3360