def gcd(x, y):
    if x == y: return x
    if x < y: y, x = x, y

    lx = len(str(x))
    ly = len(str(y))
    diff = lx - ly

    z = abs(y * 10 ** diff - x)
    z2 = abs(y * 10 ** (diff + 1) - x)
    z = min(z, z2)
    if diff > 0:
        z2 = abs(y * 10 ** (diff - 1) - x)
        z = min(z, z2)

    # zはxとyと公約数を共有する
    if z < y:
        return gcd(y, z)
    return gcd(z, y)