Harshit had exams coming up but could not concentrate as he was messed up with some mathematical calculations. He took some elements (say N) and tried number of ways to partition them into disjoint, non-empty subsets.

He gave a try and took 3 elements (N=3) in the set – {1, 2, 3} and was successful in partitioning it as he thought. The result was as follows:

Therefore now help Harshit to find number of ways ('X') of partition for different input values of 'N' ( 'N' is the number of elements taken)

*Input format: *

First line contains T number of test cases. Each of the next T lines contains the input N.

*Output Format: *

Output a single integer X, the number of ways of partition for each N.

Constraints:

1 ≤ T ≤ 10^3

1 ≤ N ≤ 25

1 ≤ X ≤ 10^19