The Tribonacci sequence is defined by

• \(T_0 = 0\), \(T_1 = 1\), \(T_2 = 1\);
• \(T_n = T_{n-1} + T_{n-2} + T_{n-3}\) for \(n \ge 3\).

Answer \(Q\) queries for \(T_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 36\)

Output

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

Example

Input

3
4
5
6

Output

4
7
13

Explanation

Using T(0)=0,T(1)=1,T(2)=1 gives T(4)=4,T(5)=7,T(6)=13.