Let F(n) be the n^th 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) + x² F(2) + x³ F(3) + ... + xⁿ F(n) + ....
= sigma(n = 0 to infinity) xⁿ F(n)

Amazingly,

A(1/2) = 1/2 + 1/2² + 2/2³ + 3/2⁴ + .... + F(n)/2ⁿ + ... = 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.

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