The cows have just learned what a primitive root is! Given a prime *p*, a primitive root <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/f203bd9f1553a2d666452cec7d6f1f4f02a817fb.png" style="max-width: 100.0%;max-height: 100.0%;"/> is an integer *x* (1 ≤ *x* &lt; *p*) such that none of integers *x* - 1, *x*<sup class="upper-index">2</sup> - 1, ..., *x*<sup class="upper-index">*p* - 2</sup> - 1 are divisible by *p*, but *x*<sup class="upper-index">*p* - 1</sup> - 1 is. 

Unfortunately, computing primitive roots can be time consuming, so the cows need your help. Given a prime *p*, help the cows find the number of primitive roots <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/f203bd9f1553a2d666452cec7d6f1f4f02a817fb.png" style="max-width: 100.0%;max-height: 100.0%;"/>.
The input contains a single line containing an integer *p* (2 ≤ *p* &lt; 2000). It is guaranteed that *p* is a prime.
primes=[]
def isPrime(number): #Works well with big numbers that are prime
    global primes
    if(number in primes):
        return True
    d = 2
    while d*d <= number:
        while (number % d) == 0:
            number //= d
        d += 1
    if number > 1:
        primes.append(number)
        return True
    else:
        return False



n=int(input())
while(n>0):
    p=int(input())
    result=0
    try:
        r=primes.index(p)
    except:
        r=-1
    if(r==-1):
        while(p>1):
            p-=1
            try:
                r=primes.index(p)
            except:
                r=-1
            if(r!=-1):
                result+=r+1
                break
            if isPrime(p):
                result+=1
    else:
        result+=r+1
    print(result)
    n-=1
