In order to pass through the wood, Vikram have to solve the following puzzle of Betaal:

Betaal has captured the Vikram family in the location pointed by the coordinate (x, y), while Vikram is on (0, 0). Now Vikram has to count the total number of increasing lattice paths from his initial position to his family and tell it to Betaal in order to set his family free. As Vikram is a loser in mathematics from childhood, he demanded you to solve this puzzle and message it secretly to him.

Problem

Given the number of test cases, t, followed by t lines. Each line contain a number, n, representing the coordinate (n, n), where Vikram family has been imprisioned. Find the number of increasing lattice paths from (0, 0) to (n, n) and print in separate lines. A path is increasing if it goes up or to the right only, i.e., a path can go from (x, y) to either (x + 1, y) or (x, y + 1).

Constraints

a. 0 < n < 31
b. number of ways < 2^64

Example

Input:
5
1
2
3
4
5

Output:
2
6
20
70
252