Existen en el mundo nuevas dimensiones a las que las persona nos hemos adaptado, los cuatro movimientos principales que conociamos ahora se combinan con movimientos diagonales. Con esta definición podemos decir que las nuevas dimensiones y las antiguas dimensiones juntas se leen en el siguiente orden: "ARRIBA", "ARRIBA DERECHA", "DERECHA", "DERECHA ABAJO", "ABAJO", "ABAJO IZQUIERDA", "IZQUIERDA" e "IZQUIERDA ARRIBA". Estas direcciones son exactas y bien definidas. Tu tarea ahora consite en determinar tu posición tras recorrer esta direcciones comenzando desde "ARRIBA" hacia la derecha tantas veces como el valor de N Recuerde que N es el número de movimientos que deberá leer y como respuesta deberá imprimir la dirección del último movimiento realizado.

Input

La primera línea del INPUT comienza con un número M que indica el número de casos del problema propuesto. (1 ≤ M ≤ 20)

Cada caso está compuesto de la(s) siguiente(s) linea(s):

La única línea de cada caso contiene el entero N ( 1 ≤ N ≤ 100 ). El número de movimientos a realizar.

Output

Salida, Imprimir la dirección del último movimiento realizado.

Entrada de ejemplo