Matcom Online Grader

Fito ahora es artesano y quiere hacer unas figuras de  cristal. Para esto tiene que cortar un cristal cuadrado de dimensiones enteras $(N \times N)$. Para esto lo pone en la mesa de cortar en donde una esquina del cristal queda en el origen y un lado queda en el eje de las $x$ y el otro en el eje de las $y$. Para cortar el cristal se siguen unas reglas básicas:

1. Solo se hacen cortes rectos entre dos puntos que están en caras diferentes del cristal y que tienen coordenadas enteras.
2. Dos cortes nunca se pueden cruzar. Pero en un punto que está en el borde se pueden unir infinitos cortes.
3. Se sigue este proceso de cortes hasta que no se pueda realizar ningún corte más.

Si se cuentan las rotaciones y reflexiones de los cortes como distintos se denomina $C(N)$ la cantidad de formas de realizar estos cortes en un cristal de $N \times N$.

Input

La primera línea contiene la cantidad de casos de prueba $K$ $(1 \leq K \leq 1000)$ seguido de $K$ líneas con un entero $N$ $(1 \leq N \leq 330)$.

Output

Por cada valor de $N$ se imprime $C(N) \texttt{ mod } 10^8$.

Sample test(s)