The Fibonacci sequence is defined by \(F_0 = 0\), \(F_1 = 1\), and \(F_n = F_{n-1} + F_{n-2}\) for \(n \ge 2\). Answer \(Q\) queries for \(F_n\).

Input

The first line contains \(Q\). Each of the next \(Q\) lines contains \(n\).

The input satisfies:

• \(1 \le Q \le 20\)
• \(0 \le n \le 90\)

Output

For each query, print \(F_n\) on its own line.

Example

Input

3
0
10
90

Output

0
55
2880067194370816120

Explanation

The requested values are F(0)=0, F(10)=55, and F(90)=2880067194370816120.