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$