def gd(n1, n2):
    if n1 < n2:
        n1, n2 = n2, n1
    if (not n2) or (n1 == n2):
        return n1
    gd(n1-n2, n2)