Time Limit Exceeded for ETF - Euler Totient Function at Spoj

In number theory, the totient φ of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n.

Given an integer n (1 ≤ n ≤ 106), compute the value of the totient φ.

For the code written below, this is giving TLE. How i can optimize this code or should i prefer some other language for this problem.
Link of the problem at spoj

test = int(input())
for t in range(test):
    n = int(input())
    result = n
    i = 2
    while i*i  1:
        result -= result/n
    print(int(result))

The way I would approach this problem is to find the prime factorization of n, and then use Euler's formula which says:

$$\varphi(n) = n \prod_{p|n}\left(1 - \frac{1}{p}\right)$$

The easiest way to do this is to find the prime factorization of n (which you are basically already doing), but store each distinct prime factor in a list. Once you are done, compute this formula for the primes, and you should have your answer fairly quickly.

StackExchange Code Review Q#136560, answer score: 4