Los azucareros del centro dejaron de mover discos de clavija a clavija después de saber la cantidad de pasos necesarios para completar toda la tarea, pero no dejaron de pensar en acertijos similares a La Torre de Hanoi. Ellos quieren aprovechar un pequeño juego inventado por Alan T. El juego consiste en ~N~ clavijas y muchas bolas. Las bolas están numeradas ~1,2,3 ...~. Las bolas parecen normales, pero en realidad son mágicas. Si la suma de los números en dos bolas adyacentes no son un número cuadrado perfecto, se empujarán entre sí con gran fuerza, por lo que nunca se pueden juntar tocándose.

El jugador debe colocar una bola en la parte superior de una clavija a la vez. Primero debe probar la bola 1, luego la bola 2, luego la bola 3 ... Si no puede poner la siguiente bola el juego termina. Ayuda al jugador a colocar tantas bolas como sea posible. Puede echar un vistazo a la imagen ya que nos muestra un mejor resultado para 4 clavijas.

Entrada:

La primera línea de la entrada contiene un número entero ~T~, que indica el número de casos de prueba ~(1 \leq T \leq 50)~. Cada caso de prueba contiene un solo número entero ~N (1 \leq N \leq 50)~, que indica el número de clavijas disponibles.

Salida

Para cada caso de prueba en la entrada, imprima una línea que contenga un número entero que indique el número máximo de bolas que se puede colocar.

Ejemplo de entrada

2
4
25

Ejemplo de salida

11
337