

modules = [i for i in range(10 ** 9 + 7, 10 ** 9 + 8, 2)]
max_n = 5 * 10 ** 6

def calc_fibs(mod):
	a = [0, 1]
	for i in range(max_n):
		a.append((a[-1] + a[-2]) % mod)
	return set(a)

q = [calc_fibs(mod) for mod in modules]

def is_fib(s):
	for (mod, fib_mods) in zip(modules, q):
		m = 0
		for ch in s.strip():
			m = (m * 10 + (ord(ch) - ord('0'))) % mod
		if m not in fib_mods:
			return False
	return True

IN = open('mushrooms.in')
open('mushrooms.out', 'w').write('\n'.join('Yes' if is_fib(IN.readline()) else 'No' for i in range(int(IN.readline()))))
