Project Euler #78: Coin partitions

_{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