FIBPOL - Fibonacci Polynomial

## 题目描述 话说上次 NaCly_Fish 好不容易解决了 $\mathsf E \color{red} \mathsf{ntropyIncreaser}$ 给她的 [这个问题](https://www.luogu.org/problem/SP31428)。 就在这时 $\mathsf E \color{red} \mathsf{ntropyIncreaser}$ 又来找她，说：“之前那个题确实太水了，我加强了一下，你来看看。” 定义函数： $$ A(x)=\sum\limits_{i=1}^\infty F_ix^i$$ 其中 $f$ 为 $\texttt{fibonacci}$ 数列，即： $$ F_0=0,F_1=1$$ $$ F_n=F_{n-1}+F_{n-2}\space(n\ge2)$$ 现在给定一个自然数 $n$，问是否存在**有理数** $x$，使得 $A(x)=n$。 如果存在，则输出 $1$，否则输出 $0$。 这下 NaCly_Fish 完全懵掉了，请你帮帮她吧。 ## 输入输出格式 ### 输入格式 第一行一个正整数 $T$，表示数据组数。 接下来 $T$ 行，每行一个自然数 $n$，意义如题目描述。 ### 输出格式 输出 $T$ 行，每行一个数 $0$ 或 $1$。 ## 说明 【样例解释】 以下为函数值表： | $x$ | $A(x)$ | | :----------- | :----------- | |$0$ | $0$ | |$\sqrt2-1$ | $1$ | |$1/2$ |$2$ | | $(\sqrt{13}-2)/3$ |$3$ | | $(\sqrt{89}-5)/8$ | $4$ | 显然对应输出 $1,0,1,0,0$。 【数据范围】 $1\le T \le 10^5$ $0\le n \le 10^{17}$

Let **F(n)** be the **_n $ ^{th} $ member of the_ Fibonacci sequence**: ``` <pre style="box-sizing: border-box; overflow: auto; font-family: Consolas, 'Liberation Mono', Menlo, Courier, monospace; font-size: 13.6px; margin-top: 0px; margin-bottom: 16px; font-stretch: normal; line-height: 1.45; padding: 16px; border-radius: 3px; word-wrap: normal; color: #333333; background-color: #f7f7f7;">``` F(<span style="box-sizing: border-box;">0) = <span style="box-sizing: border-box; color: #008080;">0</span>, <span style="box-sizing: border-box; font-weight: bold;">F</span>(<span style="box-sizing: border-box; color: #008080;">1</span>) = <span style="box-sizing: border-box; color: #008080;">1</span>, <span style="box-sizing: border-box; font-weight: bold;">F</span>(<span style="box-sizing: border-box; font-weight: bold;">n</span>) = <span style="box-sizing: border-box; font-weight: bold;">F</span>(<span style="box-sizing: border-box; font-weight: bold;">n</span>-<span style="box-sizing: border-box; color: #008080;">1</span>)+<span style="box-sizing: border-box; font-weight: bold;">F</span>(<span style="box-sizing: border-box; font-weight: bold;">n</span>-<span style="box-sizing: border-box; color: #008080;">2</span>) (<span style="box-sizing: border-box; font-weight: bold;">n</span> > <span style="box-sizing: border-box; color: #008080;">1</span>)</span> ``` ``` Consider the following Fibonacci polynomial: A(x) = x F(1) + x $ ^{2} $ F(2) + x $ ^{3} $ F(3) + ... + x $ ^{n} $ F(n) + .... = sigma(n = 0 to infinity) x $ ^{n} $ F(n) Amazingly, A(1/2) = 1/2 + 1/2 $ ^{2} $ + 2/2 $ ^{3} $ + 3/2 $ ^{4} $ + .... + F(n)/2 $ ^{n} $ + ... = 2 In this problem, we only considering the non-negative-integer value of `A(x)`. Here are some examples of `A(x)` for specific `x`. xA(x) 0 0 sqrt(2)-1 1 1/2 2 \[sqrt(13)-2\]/3 3 \[sqrt(89)-5\]/8 4Find out if `x` is rational with the given value of `A(x)`

The first line contains T, the number of test cases. The next T lines contains the value of A(x). - `0 <= Ax <= 10^17` - `1 <= T <= 100000`

- `1 if the given Ax yeilds a rational x, 0 otherwise`

5
0
1
2
3
4

1
0
1
0
0