Tammy has a circle. There are 2*n (0<n<=300) points on the circle. She wants to join every pair points using lines without crossing. But how many kinds of method can she get? The graph below indicate one kind of method Tammy can get when n=3.
Input
There are multiple test cases in the input data. In the First Line there is an Integer T(1<=T<=1000), which means the number of test cases in the input. Each of the next T lines contains an Integer n(0<n<=300), which means the number n in that case.
Output
The number of methods Tammy can get. One line per case.