本题没有可用的提交语言。

Description

Even the smallest palindrome can change the course of the future

— Galadriel, or maybe Javier

A palindrome is a string of characters that reads the same from left to right as it does from right to left. Javier, being the absent-minded boy that he is, has been thinking that "palindromio" is the correct spelling for almost a year now! To do him a favor, let's create a new definition before he realizes that he's mistaken.

A "palindromio" is a string of digits from $0$ to $9$ that is exactly one position away from being a palindrome. $101$ and $22$ are palindromes, while $100$ and $20$ are "palindromios". Not satisfied with this, Javier now wants to know how many "palindromios" can be created using exactly $n$ digits from $0$ to $9$. Help him satisfy his curiosity.

Input

The first line contains an integer $t$, ($1 \le t \le 100$), the number of questions Javier will ask you. Each of his questions will consist of a single integer $n$, the length of the "palindromio", ($1 \le n \le 5000$).

Output

For each question, you should print the number of "palindromios" of length $n$. Since this number can be very very large, Javier will be satisfied if you print it $\mod {10^9 + 7}$. This operation is performed using $\%$ in C++ and Python. Note that $(a + b) \mod P$ is the same as $(a \mod P + b \mod P) \mod P$, and a similar thing applies with the product, so you can apply the modulo operation after every operation you make to avoid overflow. If you have questions about modulos, we will answer them in the clarifications.

4
2
3
2023
13

90
900
616533557
540000000

Note

—

Problem idea: Javi

Problem preparation: Javi

Ocurrences: Novice 5