Задача 38374. magic mushrooms

There is a Large Corporation of Little Fairies on the planet Ruuk. One of the activities that her employees have been doing for centuries is planting beds with magic mushrooms. Every day, starting from the very first day of the existence of this corporation, the fairies create one new patch of mushrooms. After that, from the new bed, for two days, you can collect spores that reproduce these mushrooms, and then the bed will supply only the product itself — mushrooms.

Thus, if we denote the number of mushrooms planted in the garden created on the day number i as c_i , then it will be calculated according to the formula c_i = c_i - 1 + c_{i - 2< /sub>. So, on the first and second days, one mushroom was planted, on the third — two, the fourth — three, in the fifth — five and so on.}

Magic mushrooms are the most valuable souvenir a traveler can bring back from the planet Ruuk. Therefore, the first thing any visitor does is to search for a bed with magic mushrooms. However, lately there have been increasing reports of fake magic mushrooms. Careful investigation revealed that this is the result of the Little Big Fairy Corporation, which plant beds with mushrooms that are indistinguishable in appearance, but nowhere near as valuable as magical ones. Moreover, when creating another garden bed, these fairies plant there such a number of mushrooms that their rivals have never planted and cannot plant.

It would seem that after finding out this fact, it became easy to distinguish magic beds from fake ones. But both corporations have existed for a long time, the number of beds and mushrooms on them has long exceeded all reasonable limits. You have been asked to write a program that tells you, by the number of mushrooms in a garden, whether the garden is magical.

Input

The first line of the input file contains a single number N (1 ≤ N ≤ 1000000) — the number of studied beds. The following n lines contain one integer each a_i — the number of mushrooms in the studied beds. The size of the input file does not exceed 1 MB.

Imprint

For each number given in the input file, print "Yes" if the garden with that many mushrooms is magical, and "No" — if not. Separate your answers with line breaks.

Examples