Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Shiku Being Shiku

By mahdi.hasnat · Limits 1s, 512 MB

Guni Moira, the honest sweet shop owner of CSEmpur has recently learned about the Fibonacci sequence, and he’s already a fan <3. Now if a customer buys sweet of price equal to a Fibonacci number, Guni becomes happy and gives the sweets for free.

Shiku wants to fool Guni Moira and buy as many sweets as he wants for free. So, whatever the price is, Shiku claims that it’s a Fibonacci number (even he, himself doesn’t know 🤦). Shiku is bad. Don’t be like Shiku .

Guni doesn’t know how to verify if Shiku is wrong. So, he is asking for your help.

Input

The first line of the input contains T (1 ≤ T ≤104), the number of test cases. Then next T lines contain an integer N(0≤ N ≤ 105), the price to verify.

Output

For every test case print “YES” (without quotes) in one line if N is Fibonacci number
otherwise print “NO” (without quotes) in one line.

Sample

InputOutput
5
0
1
2
4
100000
YES
YES
YES
NO
NO

Note: In mathematics, the Fibonacci numbers, commonly denoted FnF_n, form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F0=0,F1=1F_0 = 0 , F_1 = 1
and
Fn=Fn1+Fn2F_n = F_{n-1} + F_{n-2} for nn > 1

The first few numbers of these sequence are 0,1,1,2,3,5,8,13,21,34,55,0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \cdots

Discussion

Statistics


94% Solution Ratio

InxtinctEarliest, Feb '20

SyedaSohiFastest, 0.0s

InxtinctLightest, 131 kB

joe.masterShortest, 115B

Submit

Login to submit

Toph uses cookies. By continuing you agree to our Cookie Policy.