Ravi and Sunil are friends. Ravi has a very old phone which he wants to give to Sunil on his birthday. Ravi will give the phone to Sunil only Sunil gives the answer to one question.

The question is how many distinct numbers of $N$ digits can be formed using the keypad of that phone and also meets the following condition :

- The absolute difference of two successive pressed digits must be a prime.
- The first digit of the number must be non-zero.

Sunil is your brother. Help him to get that phone.

This is what a keypad would look like, please note you CANNOT press the * and # buttons.

Since the answer will be large so print your answer modulo $10^9+7$.

Input :
The first line of the input contains a single integer $T$, the number of test cases.
Next $T$ lines contain a single integer $N$ .

Output:
Print the required result in a new line for each query.

Constraints :
$1\leq T \leq5\\0 \leq N \leq 10^5$

Author: Chandan Kumar Sharma