Following is the recursive definition of Fibonacci sequence:
$$
F_i=
\begin{cases}
0& \text{i = 0} \\
1& \text{i = 1} \\
F_{i-1} + F_{i-2}& \text{i > 1}
\end{cases}
$$
Now we need to check whether a number can be expressed as the product of numbers in the Fibonacci sequence.
Input
There is a number \(T\) shows there are \(T\) test cases below. ($T \leq 100,000$)
For each test case , the first line contains a integers n , which means the number need to be checked.
$0 \leq n \leq 1,000,000,000$
