Musical Notes

Time Limit: 1 Second    Memory Limit: 65536 KB

We want to create a musical score consisting of a succession of notes. There are only two choices for the pitch of each note: each note has either a low sound or a high sound. There are also only two choices for the duration of each note: each note is either short or long. Each short note takes 1 second, and each long note takes 2 seconds. We have the following constraints:

• a) The total duration of the musical score should be a given integer n.
• b) The number of low short notes should be the same as the number of high short notes.
• c) The number of low long notes should be the same as the number of high long notes.
• d) There should be at least as many long notes as there are short notes.
• e) Low and high notes must alternate.
• f) The first note should be low.

Given an even integer n, we want to know the number of possible music scores satisfying the above.

For example, with n = 6, there are 4 possibilities:

2211, 2112, 1221, 1122

(Each note is represented by its duration, and the high notes are shown in bold.)

With n = 8, there is only 1 possibility: 2222

Input

The first line of the input includes the number of test cases t, 1≤t≤10000. On each next line, a test case is specified by giving the even integer n, 2≤n≤100.

Output

For each test case, print one line containing the answer to the question.

Sample Input

5
6
8
10
12
62

Sample Output

4
1
9
37
30823385424

Submit

Source: 13th Iran Nationwide Internet Contest - Final