It's time for CCC! This year, you are participating in CCC remotely, and for some reason, you are allowed to consult ChatGPT during the CCC. The first question asks you to, for ~T~ integers, identify whether they are composite Fibonacci numbers. However, you have no idea what they are. You seem to recall something about composite numbers and Fibonacci numbers, so you ask ChatGPT some questions to get oriented.

What is a Fibonacci number? ChatGPT helpfully says the following:

A Fibonacci number is a number in a sequence of numbers called the Fibonacci sequence, which is named after the Italian mathematician Leonardo Fibonacci. The Fibonacci sequence is defined as follows:

The first two numbers in the sequence are 0 and 1.
Each subsequent number in the sequence is the sum of the previous two numbers.
For example, the first few numbers in the Fibonacci sequence are: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, etc.

The Fibonacci sequence has many interesting properties and appears in various areas of mathematics, including number theory, geometry, and probability. It is also of interest to biologists, since the Fibonacci sequence appears in the arrangement of leaves and branches on plants, the branching of trees, and the arrangement of scales on pinecones and pineapples.

What is a composite number? ChatGPT helpfully says the following:

A composite number is a positive integer that can be divided evenly by at least one integer other than itself and 1. For example, 4 is a composite number because it can be evenly divided by 2 (4 ÷ 2 = 2). 6 is a composite number because it can be evenly divided by 2 (6 ÷ 2 = 3) or 3 (6 ÷ 3 = 2).

On the other hand, a number that cannot be divided evenly by any integer other than itself and 1 is called a prime number. For example, 2, 3, 5, 7, and 11 are prime numbers, since they have no other positive integer factors besides 1 and themselves.

Composite numbers are also sometimes referred to as "non-prime" or "composite" numbers. There are an infinite number of composite numbers, but there are only a finite number of prime numbers.

So what is a composite Fibonacci number? ChatGPT says the following:

A composite Fibonacci number is a positive integer that can be obtained by concatenating two or more Fibonacci numbers together. For example, 138 is a composite Fibonacci number because 13 and 8 can be concatenated together to form 138.

On the other hand, 8 is not a composite Fibonacci number, even though it is a composite number and a Fibonacci number.

Composite Fibonacci numbers were first made famous in the Mock CCC '23 1, where they appeared in the problem Composite Fibonacci Numbers.

You're a little confused as to why 8 isn't a composite Fibonacci number, but you go along with their definition.

Constraints

~1 \le T \le 10^5~

~1 \le N \le 10^5~

In tests worth 5 marks, ~N~ will not contain any of the digits ~4~, ~6~, ~7~, or ~9~.

Input Specification

The first line contains one integer, ~T~.

Each of the next ~T~ lines contains one integer, ~N~.

Output Specification

Output ~T~ lines. On the ~i~th line, if the given integer is a composite Fibonacci number, output YES. Otherwise, output NO.

Sample Input

3
138
8
100

Sample Output

YES
NO
YES