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

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.

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.

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

otherwise print “NO” (without quotes) in one line.

Input | Output |
---|---|

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

**Note**: In mathematics, the Fibonacci numbers, commonly denoted $F_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,

$F_0 = 0 , F_1 = 1$

and

$F_n = F_{n-1} + F_{n-2}$ for $n$ > 1

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

94% Solution Ratio

InxtinctEarliest,

SyedaSohiFastest, 0.0s

InxtinctLightest, 131 kB

joe.masterShortest, 115B

Login to submit

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