This problem is a programming version of Problem 78 from projecteuler.net
Let represent the number of different ways in which coins can be separated into piles. For example, five coins can separated into piles in exactly seven different ways, so .
OOO O O
OO OO O
OO O O O
O O O O O
How many different ways can coins be separated into piles?
As answer can be large, print
First line of the input contains , which is number of testcases.
Each testcase contains .
Print the output corresponding to each testcase on a new line.