Hongjun's Royal Guard

Time limit1sMemory limit128 MB

Summary

Count permutations of N distinct elements where every interior element is a local extremum (both neighbors larger or both smaller); N is at most 20.

Level: Medium6 of 10
Topics: Dynamic programming, Combinatorics, Brute force, Bit manipulation
Solved: No attempts yet

Problem

King Hongjun of the Hongjun Kingdom has $N$ royal guards protecting him. All guards have distinct heights. When Hongjun lines them up, he considers an arrangement good-looking if, for every guard except the two at the ends, the two guards standing immediately on either side are both taller than that guard or both shorter than that guard.

For example, suppose seven guards have heights 160, 162, 164, 166, 168, 170, and 172 cm. If they stand in the order 166 172 164 170 160 168 162, then every guard except the two at the ends has both neighbors taller than itself or both shorter than itself, so Hongjun finds this arrangement good-looking.

Hongjun would be bored by seeing the same arrangement every day, so he wants a new good-looking arrangement each day. That is, given $N$ guards, he wants to know how many distinct good-looking arrangements are possible.

For example, with four guards whose heights we denote 1, 2, 3, 4 for convenience, the following 10 arrangements are good-looking:

1324, 2143, 3142, 2314, 3412, 4231, 4132, 2413, 3241, 1423

Given the number of guards $N$ , write a program that computes the number of possible good-looking arrangements.

Input

The first line contains the number of test cases $T$ ( $1 \le T \le 1{,}000$ ).

Each test case is a single line containing a natural number $N$ , the number of guards ( $1 \le N \le 20$ ).

Output

For each test case, print the number of possible good-looking arrangements on its own line.

Examples1

Example 1
Input
```
4
1
3
4
20
```
Expected output
```
1
4
10
740742376475050
```