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
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 £
Print the values corresponding to each test case.