There are n people busy with arranging the upcoming Inter Department Programming Contest (IDPC) 2016.They call for the final meeting to finalize the contest rules. They select a room that is large enough to accommodate n people. Every person is wearing shoes of distinct color (each person has shoes of the same color on both feet but is different from another person). Before starting the meeting everyone took off their shoes outside the room. But suddenly load shedding occurs so that all of them end the meeting and begin leaving the room. In the dark, they are have trouble recognizing their shoes as all of them are of the same size. So every person picked two shoes at random and wore them without identifying which one is for the left feet and which one is for right. Now all of them are standing sequentially from 1 to n.

They create a color pattern of shoes as they stand next to each other. Since load shedding is a common issue, tell me what is the total number of possible patterns that can be created?

Input

First line of input contains test case T (1 <= T <= 10). Each of the next T lines contains the value of n (1 <= n <= 10).

Output

For each test case print the total number of possible patterns.

Sample

Input

Output

2
1
2

1
6

For the second test case, suppose first person was wearing two black shoes and second person was wearing two white shoes before the meeting started. After load shedding, the possible ways of their color patterns are given:

P1 Left P1 Right P2 Left P2 Right
Black Black White White
Black White Black White
Black White White Black
White Black Black White
White Black White Black
White White Black Black

This problem was authored for Inter Department Programming Contest 2016 at Jahangirnagar University and is being hosted on Toph per author's request.