The Head Chef has been playing with Fibonacci numbers for long . He has learnt several tricks related to Fibonacci numbers . Now he wants to test his chefs in the skills . 
A fibonacci number is defined by the recurrence :
f(n) = f(n-1) + f(n-2) for n > 2 and f(1) = 0 and f(2) = 1 .  
Given a number  A   , determine if it is a fibonacci number.

Input

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The only line of each test case contains a single integer  A  denoting the number to be checked .


Output

For each test case, output a single line containing "YES" if the given number is a fibonacci number , otherwise output a single line containing "NO" . 


Constraints

1 ≤ T ≤ 1000
1 ≤ number of digits in A  ≤ 1000
  The sum of number of digits in A in all test cases   <= 10000.  


Example
Input:
3
3
4
5

Output:
YES
NO
YES

Explanation
Example case 1. The first few fibonacci numbers are 0 , 1 , 1 , 2 , 3 ,5 , 8 , 13 and so on and the series is increasing . Only 3 and 5 appear in this series while 4 does not appear in the series .
import sys

arr=sys.stdin.read().split()

N=int(arr[0])

nos=[]
nos1=[]
k=0
for i in range(0,N):
	k+=1
	nos.append(int(arr[k]))
	nos1.append(int(arr[k]))

nos1.sort()

def bin_search(arr,start,end,x):
	mid=(start+end)/2
	if(end<start):
		return -1
	if(arr[mid]==x):
		return mid
	if(arr[mid]>x):
		return bin_search(arr,start,mid-1,x)
	else:
		return bin_search(arr,mid+1,end,x)

def fib_gen_check(limit):
	a=0
	b=1
	for i in range(5000):
		if(bin_search(nos1,0,N-1,b)!=-1):
			for j in range(0,N):
				if(nos[j]==b):
					nos[j]=-1
		tmp=b
		b=a+b
		a=tmp

fib_gen_check(5000)
for i in range(0,N):
	if(nos[i]==-1):
		print("YES")
	else:
		print("NO")