def gcd(a:int,b:int)->int:
    """ Euclid's algorithm for GCD of two integers
    """
    if a<=0 or b<=0:
        raise Exception('only positive integers as input to gcd')
    while True:
        if a==b:
        
            return a
        elif b==1 or a==1:
            return 1
        elif a>b:
            b = a-b
            a = a-b
        else:
            b = b-a
            a = b+a