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