Panda worked very hard all his lifetime to save himself a lot of wealth (a few million panda dollars). He fears that his wealth is not safe from the thieves of Pandaland. So to keep his earnings safe, Panda bought a big new safe (There are no banks in Pandaland yet). The safe has a lock of the following resemblance.

SAFE

Now Panda wants to choose a passcode for the safe.A valid passcode can be any sequence of digits (0-9), such that consecutive digits of the sequence share an edge in the given lock layout.

For Example: 563 is a valid passcode. But 536 is not a valid passcode (because 5 and 3 do not share an edge).Also 55 is an Invalid passcode. Panda wants his passcode to be of length n. He just wonders, how many different valid passcodes are possible of length n. Panda being lazy wants you to help him out. Since the answer can be huge output the number mod 1000000007.

INPUT:

First line contains an integer T denoting the number of test case(s). Each test case consists of an integer n, denoting the length of the passcode.

OUTPUT:

For each test case output answer in separate line.

Constraints:

1 <= T <= 1,000

1 <= N <= 100,000

Problem Author - Rishi Kundu