FiboBinary

Time Limit: 1 Second    Memory Limit: 131072 KB

Milad likes to find hidden structures in numbers and one of the latest structures he found, is FiboBinary structure. He calls number n a FiboBinary number if there is an integer i for which the following relation is true:

n = fib(i) + bin(i),

wherefib(i)means the ith Fibonacci number and bin(i) means number of “1”s in the binary form of number i. Your task is to write a program which gets a number and check if it is a FiboBinary number or not.

Note: fib(1)= fib(2) = 1and fib(k)= fib(k-1) + fib(k-2) for each k > 2.

Input

First line of the input contains an integer N which is number of test cases. Each of the following N lines contains an integer n to be checked (1 <= n <= 10000).

Output

For each test, print “Yes” if it is a FiboBinary number, otherwise print “No”.

Sample Input

4
4
5
6
7

Sample Output

Yes
No
No
Yes

Submit