Infinite Triangular Graph Paths

We define an infinite triangular graph as follows: the nodes are arranged in rows, where the 1st row contains node 1, the 2nd row contains nodes 2 and 3, the 3rd row contains nodes 4, 5 and 6, and so on. In general, the r-th row contains r nodes. Two adjacent rows are connected in a way that every node in row r connects to two nodes in row r+1; specifically, the node in the j-th position of row r connects to the j-th and (j+1)-th nodes in row r+1.

You are asked to calculate the number of distinct paths from the top node (node 1) to a given node u. Let the node u be located in row r and at position c in that row. Note that the numbering of nodes starts from 1 and each row r has exactly r nodes. It can be proven that the number of distinct paths is given by the binomial coefficient

[ \binom{r-1}{c-1} ]

since it takes exactly (r-1) moves to reach row r from the top, and exactly (c-1) of these moves must be moves to the right.

There are T queries. For each query, you are given an integer u, and you need to output the number of distinct paths to node u.

inputFormat

The first line contains a single integer T, the number of queries.
Each of the next T lines contains a single integer u, representing the target node number in the infinite triangular graph.

outputFormat

For each query, output a single line containing the number of distinct paths from node 1 to node u.

sample

3
1
5
6

1
2
1