Ahora estás en HSFZ, el famoso reino de las matemáticas. Por lo tanto, debes resolver algunos problemas matemáticos. Se te dan dos enteros positivos $p$ y $q$. Tu tarea es construir enteros positivos $a, b, c, d$ tales que $1 \le a, b, c, d \le 10^7$ y $$ \frac{a^3 + b^3}{c^3 + d^3} = \frac{p}{q} $$

Entrada

Cada caso de prueba contiene varios casos de prueba. La primera línea contiene un entero $t$ ($1 \le t \le 10^6$), que indica el número de casos de prueba. Para cada caso de prueba, una sola línea contiene dos enteros $p, q$ ($1 \le p, q \le 10^4$).

Salida

Para cada caso de prueba, imprime una línea que contenga cuatro enteros $a, b, c, d$ ($1 \le a, b, c, d \le 10^7$). Se puede demostrar que siempre existe una solución bajo las restricciones anteriores.

Ejemplos

Entrada 1

2
1 1
9 28

Salida 1

1 1 1 1
1 2 1 3