We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.

- All Contests
- ProjectEuler+
- Project Euler #78: Coin partitions

# Project Euler #78: Coin partitions

# 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
```