Magic Mushrooms

On the planet Ruuk there is the Big Corporation of Little Fairies. Its fairies have long planted beds of magic mushrooms. From the first day the corporation existed, the fairies create one new bed every day. For two days after a new bed is made, its spores can be collected. After that, the bed produces only the mushrooms themselves.

If $c_i$ is the number of mushrooms planted on the bed created on day $i$, then $c_i = c_{i-1} + c_{i-2}$. The first and second days each had one mushroom, the third had two, the fourth had three, the fifth had five, and so on.

Magic mushrooms are the most valuable souvenirs a traveler can bring from Ruuk, so every visitor first looks for a magic mushroom bed. Lately, however, reports of fake magic mushrooms have become more frequent. A careful investigation showed that the Small Corporation of Big Fairies is behind them. It plants beds that look identical but are far less valuable. When it creates a bed, it plants a number of mushrooms that its rivals have never planted and will never be able to plant.

Write a program that, given the number of mushrooms on a bed, determines whether that bed is magic.

The first line contains one integer $N$ ($1 \le N \le 1,000,000$), the number of beds to check. Each of the next $N$ lines contains one integer $a_i$, the number of mushrooms on a bed being checked. The input file is at most 1 MB.

For each number in the input, print Yes if a bed with that many mushrooms is magic, and No otherwise. Print each answer on its own line.