def gcd(q, a):
    while q >= a:
        q = q - a
    if q != 0:
        if gcd(a, q) == 0:
            return q
        else:
            return gcd(a, q)
    else:
        return q

def eulersPhi(x):
    t = 1
    ans = 0
    while t < x:
        if gcd(t, x) == 1:
            ans=ans+1
        else:
            pass
        t=t+1
    return ans

print(eulersPhi(13))