## FIBPOL - Fibonacci Polynomial

Let F(n) be the nth member of the Fibonacci sequence:

``````F(0) = 0, F(1) = 1,
F(n) = F(n-1)+F(n-2) (n > 1)``````

Consider the following Fibonacci polynomial:

A(x) = x F(1) + x2 F(2) + x3 F(3) + ... + xn F(n) + ....
= sigma(n = 0 to infinity) xn F(n)

Amazingly,

A(1/2) = 1/2 + 1/22 + 2/23 + 3/24 + .... + F(n)/2n + ... = 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 4

Find out if `x` is rational with the given value of `A(x)`

### Input

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`

### Output

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

### Example

```Input:
5```
`0`
`1`
`2`
`3`
`4`
```Output:
1```
`0`
`1`
`0`
`0`

 < Previous 1 2 Next > akhand_mishra: 2019-12-05 10:14:38 credits to project Euler hacking_bot: 2018-03-20 14:10:19 For Those in doubt refer Project Euler problem 137 ans THIS --> https://oeis.org/A081018 anirudnits: 2017-10-31 09:36:16 is Ax always an integer? bolderic: 2017-08-23 03:34:28 Have to say I got a feeling back to my senior high school doing some hard sequence problem holmesherlock: 2017-04-01 21:45:31 excellent prob,,figured out the solution very early but getting it accepted costed me more than 20 WA.. Aditya Paliwal: 2017-02-01 16:25:30 Last edit: 2017-02-01 17:26:01 spartax: 2016-12-01 17:35:01 for c/cpp users, use long double rahulpadhy: 2016-08-17 08:02:48 Hey Piyush.. This is my submission id : http://www.spoj.com/submit/FIBPOL/id=17521569 Can you please tell as to where I am going wrong ? Re: You have WA for some large cases. Approach is correct. Last edit: 2016-08-17 13:55:35 Min_25: 2016-06-10 16:13:46 Almost the same as Project Euler 137. It should be mentioned in the description or in the Resource. Last edit: 2016-06-10 16:27:19 Piyush Kumar: 2016-06-10 15:18:09 Test cases have been updated. Sorry for the inconvenience!