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 #31: Coin sums

# Project Euler #31: Coin sums

# Project Euler #31: Coin sums

_{This problem is a programming version of Problem 31 from projecteuler.net}

In England the currency is made up of pound, , and pence, , and there are eight coins in general circulation:

It is possible to make in the following way:

How many different ways can be made using any number of coins? As the result can be large print answer mod

**Input Format**

The first line contains an integer , i.e., number of test cases.

Next lines will contain an integer .

**Note:** N is given as and not

**Constraints**

**Output Format**

Print the values corresponding to each test case.

**Sample Input**

```
3
10
15
20
```

**Sample Output**

```
11
22
41
```