def phi(n):
    res = 0
    for i in range(n):
        if gcd(i, n) == 1:
            res += 1
    return res

def gcd(n, m):
    if m == 0:
        return n
    return gcd(m, n % m)