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

Sample Output

11
22
41