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.
输入解释
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$