def gcd(a,b): 
    while b: 
        a, b = b, a % b 
    return a 
def totient(n): 
    if not (type(n)==type(1) and n>=0): 
        raise ValueError, 'Invalid input type' 
    tot,pos = 0, n 
    while pos>0: 
        if gcd(pos,n)==1: tot += 1 
        pos -= 1 
    return tot