Little Pandey is extremely protective of his wing-mates, i.e., people living in his wing. There are N people living in his wing, with ranks 1 through N, one person with each rank.
Smaller rank means a better wing-man.
The same for N rooms.
They are numbered 1 through N and better rooms have smaller numbers.
Initially, person ranked 1 lives in room #1, person ranked 2 lives in room #2, and so on.

Now, Pandey's best friend GJ wants to experiment with their living arrangement. He wants to arrange them such that no wing-mate will be at room matching his rank. Additionally, each wing-mate will be upset if some worse wing-mate gets a better room.
For each arrangement one's rage is increased by the number of worse wing-mates with better rooms.

To irritate everyone, GJ will now try every possible way to arrange Pandey's wing-mates to satisfy the condition "no wing-mate at room matching his rank".
Note that without this condition there would be N! possible arrangements.

You've to find the total sum of the rage of the wing-mates.

Input format:
The first line contains an integer T, denoting the number of test cases.
Each of the next T lines contains an integer N, denoting the number of people in the wing.

Output format:
For each test case find the total rage of the wing-mates.
Print each answer in a separate line.

Constraints:
1 ≤ T ≤ 8
1 ≤ N ≤ 8 (40 points)
9 ≤ N ≤ 16 (60 points)

SAMPLE INPUT
2
2
3

SAMPLE OUTPUT
1
4

见题面

见题面