Description

Fib定义为Fib(0)=0,Fib(1)=1,

对于n>=2,Fib(n)=Fib(n-1)+Fib(n-2)

现给出N，求Fib(2^n).

Input Format

本题有多组数据。第一行一个整数T，表示数据组数。

接下来T行每行一个整数N，含义如题目所示。

n<=10^15,T<=5

Output Format

输出共T行，每行一个整数为所求答案。

由于答案可能过大，请将答案 mod 1125899839733759 后输出

2
2
31

3
343812777493853