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

#include <stdio.h>
#include <stdlib.h>
int step[12] = {}, ans[12] = {0, 1};
void Backtracking(int now) {
	if(now >= 12)
		return;
	if(now > 0) {
		int i, f = 1, c = now;
		int tmp = 2, count = 2;
		for(i = 2; i <= c+1; i++)
			f *= i;
		for(i = 0; i < c-1; i++) {
			if(step[i] == step[i+1] && step[i] == 2)
				count++, tmp *= count;
			else {
				if(step[i] == 2)
					f /= tmp, tmp = 2, count = 2;
			}
		}		
		if(step[i] == 2)
			f /= tmp, tmp = 2, count = 2;
		ans[c+1] += f;
	}
	step[now] = 0;
	Backtracking(now+1);
	step[now] = 2;
	Backtracking(now+1);
}
int main() {
	int t, n;
	Backtracking(0);
	scanf("%d", &t);
	while(t--) {
		scanf("%d", &n);
		printf("%d\n", ans[n]);
	}
    return 0;
}