Background

Working in a boutique folding and putting in order T-shirts according to their sizes seems very easy. But is it really so simple?

The Problem

Given n objects of different sizes, how many different arrangements can be done using relationships "<" and "="?

For instance, with 2 objects, A and B, we have 3 possible arrangements:

A=B     A<B     B<A

With 3 objects, A, B and C, you must conclude that 13 different arrangements exist:

A=B=C     A=B<C     A<B=C     A<B<C     A<C<B     A=C<B     B<A=C     B<A<C     B<C<A     B=C<A     C<A=B     C<A<B     C<B<A

The Input

The first line of the input contains an integer, t, indicating the number of test cases. For each test case, one line appears, that contains a number n, 1<=n<=11, representing the number of objects.

The Output

For each test case, the output should contain a single line with the number representing the different arrangements you can do with n objects.

Sample Input

4
1
2
3
4

Sample Output

1
3
13
75

OMP'11
Facultad de Informatica
Universidad de Murcia (SPAIN)