B :: 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 30823385424Submit
Source: 13th Iran Nationwide Internet Contest - Final