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 .
OOOOO
OOOO O
OOO OO
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
Input Format
First line of the input contains , which is number of testcases. Each testcase contains .
Constraints
Output Format
Print the output corresponding to each testcase on a new line.
Sample Input
2
5
6
Sample Output
7
11