Primitive Roots

We say that integer x, 0 < x < n, is a primitive root modulo n if and only if the minimum positive integer y which makes x^y = 1 (mod n) true is φ(n) .Here φ(n) is an arithmetic function that counts the totatives of n, that is, the positive integers less than or equal to n that are relatively prime to n. Write a program which given any positive integer n( 2 <= n < 1000000) outputs all primitive roots of n in ascending order.

Multi test cases.
Each line of the input contains a positive integer n. Input is terminated by the end-of-file seperator.

For each n, outputs all primitive roots of n in ascending order in a single line, if there is no primitive root for n just print -1 in a single line.

4
25

3
2 3 8 12 13 17 22 23

BestCoder Round #8