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)