Xiao Bai and Xiao Lan are attending a math class together. After class, the teacher leaves an assignment to find the general term formula for the following sequence:

$A_0 = 0$

$A_1 = 1$

$A_{2i} = A_i (\text{for any integer } i > 0)$

$A_{2i+1} = A_i + A_{i+1} (\text{for any integer } i > 0)$

As a math enthusiast, Xiao Bai quickly calculates the general term formula for this sequence. Xiao Bai tells Xiao Lan that they have solved it, but to prevent Xiao Lan from copying the homework, Xiao Bai does not want to reveal the formula. To prove to Xiao Lan that they have indeed solved the problem and to show off, Xiao Bai comes up with a brilliant method: Xiao Lan says a positive integer $N$, and Xiao Bai states the value of $A_N$. If Xiao Bai can quickly provide the correct answer even when $N$ is very large, it proves that Xiao Bai has indeed obtained the formula. However, this method has a major flaw: Xiao Lan does not know how to solve it and cannot verify whether Xiao Bai's answer is correct. As Xiao Lan's friend, can you help Xiao Lan?

Input

The first line of the input file contains a single positive integer $T$, representing the number of test cases.

The next $T$ lines each contain a non-negative integer $N$.

Output

The output file contains $T$ lines.

The $i$-th line should contain a number without leading zeros, whose value is equal to $A_n$ (where $n$ is the integer read from the $i+1$-th line of the input).

Constraints

For 20% of the data, $N \le 10^8$.

For 50% of the data, $N \le 10^{13}$.

For 100% of the data, $T \le 20, N \le 10^{100}$.

Examples

Input 1

3
1
3
10

Output 1

1
2
3

A_0 = 0