Matcom Online Grader

Fito está de visita en WaveLand en casa de su hermana Fitica. Sus sobrinos están estudiando matemática y Fito quiere ayudarlos. Pero al ver el problema Fito no entiende bien, ya que en WaveLand el sistema numérico no es en base $10$ sino $11$. Por lo que un número está compuesto por los dígitos $0,1,2,3,4,5,6,7,8,9,A$. Nuestra tarea es ayudar a Fito a resolver el siguiente problema:

Cuantos números Wave hay de $N$ dígitos en base $11$? Un número es Wave cuando todos sus dígitos adyacentes y los extremos difieren solamente en una unidad. Por ejemplo $212343$ es un número wave de $6$ dígitos, no son wave $A0A$ ni $234$.  Diga la respuesta módulo $4294967143$.

Input

La primera línea contiene un entero $T$ que representa la cantidad de casos de prueba $(1 \leq T \leq 20000)$. Cada una de las siguientes $T$ líneas contiene un entero $N$ $(1 \leq N \lt 2^{64})$, representando la cantidad de dígitos.

Output

Por cada caso de prueba debe de imprimir la respuesta.

Sample test(s)