Description
In computational mathematics, the Catalan numbers form a sequence of natural numbers that occur in various counting problems.
In programming contests, we usually use one of the two following forms of Catalan Number:
1. Division Version:
2. Non-division Version:
It's useful in many problem. There are some examples:
● The number of containing n pairs of parentheses which correct matched:
For n = 3, C(3) = 5:
((()))
()(())
()()()
(())()
(()())
● The number of full binary trees with n + 1 leaves
For n = 3, C(3) = 5:
● The number of different ways a convex polygon with n+2 sides can be cut into triangles by connecting vertices with straight lines.
For n = 4, C(4) = 14:
Input
The first line of the input is an integer Z (Z ≤ 500), which means the number of test cases. For each test case, one line contains one non-negative integer N (N ≤ 500). It is guaranteed that the number of digits of the largest Catalan number in this problem is less than 300.
Output
For each test case, output the test case number and the N-th Catalan number.