Counting Music Scores

Time limit2sMemory limit512 MB

Summary

Count scores over two pitches and two durations with n seconds total, balanced pitch counts, at least as many long notes as short, and alternating pitches starting low.

Level: Medium5 of 10
Topics: Combinatorics, Dynamic programming, Math
Solved: No attempts yet

Problem

You build a musical score by writing notes one after another. Each note has one of two pitches, low or high, and one of two durations, short or long. A short note lasts 1 second and a long note lasts 2 seconds. The score must satisfy all of the following.

a) The total duration of the score is a given integer $n$ seconds.
b) The number of low short notes equals the number of high short notes.
c) The number of low long notes equals the number of high long notes.
d) The number of long notes is at least the number of short notes.
e) Low notes and high notes alternate.
f) The first note is low.

Given an even integer $n$ , count the scores that satisfy every condition. Writing each note as its duration, the 4 scores for $n = 6$ are 2211, 2112, 1221 and 1122. Conditions e and f force every odd numbered note to be low and every even numbered note to be high. For $n = 8$ the only score is 2222.

Input

The first line contains the number of test cases $t$ ( $1 \le t \le 10000$ ).
Each of the next $t$ lines contains one even integer $n$ ( $2 \le n \le 100$ ).

Output

For each test case, print on its own line the number of scores that satisfy every condition. The answer is smaller than $2^{63}$ .

Examples3

Example 1
Input
```
5
6
8
10
12
62
```
Expected output
```
4
1
9
37
30823385424
```
Example 2
Input
```
1
2
```
Expected output
```
0
```
Example 3
Input
```
1
62
```
Expected output
```
30823385424
```