DG (Departmental Gathering) is coming….

As one of the most famous girls in the college everybody is smitten with Harshada and wants to give

her roses. But Harshada is only into coders , therefore she sends out word that she would accept

roses from the nth guy only if he brings her x roses such that ‘x’ is the nth term of the sequence

given below. One of your friends is madly in love with Harshada but he is not so much of a coder.

Help him show his coder metal to the girl of his dreams.

1, 2, 2, 4, 8,12………..
Constraints:
1 ≤ T ≤ 100
1 ≤ n ≤ 20
Input

First line of input contains a variable T, number of test cases. Each test case contains a single integer input n.

Output

For each test case output a single line that has an integer value x which in the nth term of the given series.

SAMPLE INPUT
3
1
5
10

SAMPLE OUTPUT
1
8
10476

Explanation

There are 3 test case

Test case 1: 1st guy has to give 1 rose.

Test case 2: 5th guy has to give 8 roses.

Test case 3: 10th guy has to give 10476 roses.

You don’t want to be the 10th guy, do you? :p

见题面

见题面