Given a positive integer 'N' , find the number of positive integers less than or equal to N, which are relatively prime to N.
Two positive integers 'a' and 'b' are called relatively prime if gcd(a,b) = 1 (Where gcd is Greatest Common Divisor).
The first line consists of a number 't' which specifies the number of test cases. 1<=t<=10000. 't' lines follow with a number 'n' on each line. 1<=n<=10^6
For each test case, output the number of positive integers less than or equal to N which are relatively prime to N.
Input: 5 1 2 4 10 20 Output: 1 1 2 4 8
|Time Limit:||0.4285 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, JAVA, PYTH, CS2, PAS fpc, PAS gpc, RUBY, PHP, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, SQL, TEXT|
Fetching successful submissions