RANJAN03 - Vikram & Betaal

no tags 

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


Added by:abhiranjan
Date:2010-09-28
Time limit:0.400s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:IIITM Local Contest