A. Decreasing Trees
time limit per test
1 second
memory limit per test
125 megabytes
input
standard input
output
standard output

You are given a labeled tree on $$$n$$$ vertices with labels $$$1\dots n$$$. Vertex $$$1$$$ is the root, and along every edge from a vertex to its parent, labels strictly decrease (equivalently, labels strictly increase along any path from the root to a vertex). Formally, if $$$p(v)$$$ is the parent of $$$v$$$, then $$$\text{label}[v] \gt \text{label}[p(v)]$$$, and $$$\text{label}[1] = 1$$$.

Input

The first line contains a single integer $$$t$$$ $$$(1 \le t \le 2000)$$$ — the number of test cases. Each test case consists of a single integer $$$n$$$ $$$(1 \le n \le 20)$$$.

Output

For each test case, print a single integer — the number of decreasing trees on $$$n$$$ labeled vertices.

Example
Input
4
1
2
3
4
Output
1
1
2
6
Note
  • For $$$n = 1$$$: there is exactly one valid tree: just vertex 1.
  • For $$$n = 2$$$: there is exactly one valid tree: $$$1 \to 2$$$.
  • For $$$n = 3$$$: there are exactly two valid trees: the star $$$1 \to 2, 1 \to 3$$$ and the chain $$$1 \to 2 \to 3$$$.
  • For $$$n = 4$$$: there are exactly six valid trees.