\begin{problem}{Колобки против Энигмы}{стандартный ввод}{стандартный вывод}{2 секунды}{256 мегабайт}

Иностранный торговец животными Карбофос успел найти покупателя похищенного полосатого слона. Он отправил ему в Германию шифрованное сообщение.

В тот же день братьям детективам доложили о пропаже из столичного музея шифровальной машины <<Энигма 43>>. Шеф уверен, что это не совпадение.

<<Энигма 43>> всегда генерирует целое число $\overline{a_1a_2\ldots a_n}$ ($0 \le a_i \le 9$, $a_1 \neq 0$) длины $n$, обладающее особым свойством: ни у каких двух соседних пар цифр не совпадает НОД (наибольший общий делитель). Другими словами, для любой тройки подряд идущих цифр $\overline{a_i a_{i+1} a_{i+2}}$ верно, что $\gcd(a_i, a_{i+1}) \neq \gcd(a_{i+1}, a_{i+2})$. Любое число, обладающее таким свойством, может быть сгенерировано. В этой задаче $\gcd(0, 0) = 0$.

В сообщении могут содержаться важные для следствия данные, но его проблематично восстановить. Коллега предложил воспользоваться полным перебором.

Помогите братьям Колобкам посчитать количество сообщений, которые Карбофос мог отправить с помощью <<Энигма 43>>. Так как ответ может быть большим, посчитайте его по модулю $10^9 + 7$.

\begin{center}
\includegraphics{pic5.png}
\end{center}


\InputFile
В первой строке дано целое число $t$ ($1 \le t \le 5000$)~--- количество наборов входных данных.

В единственной строке каждого набора дано целое число $n$ ($2 \le n \le 10^{18}$)~--- длина сообщения.


\OutputFile
Для каждого набора данных выведите единственное число --- количество чисел длины $n$, которые могли быть сгенерированы Энигмой по модулю $10^9 + 7$.


\Example

\begin{example}
\exmpfile{example.01}{example.01.a}%
\end{example}

\Note
Для $n=3$ некоторые числа, которые могли быть сгенерированы Энигмой: $124$, $322$, $504$, $661$, $993$

\end{problem}

