Pelotazo urbanístico
Moisés Eña está dispuesto a hacerse rico gracias al ladrillo. Ha comprado un gran terreno en un pueblecito bien comunicado y planea hacer una urbanización de lujo. Hace algún tiempo intentó forrarse haciendo pisos baratos para gente con recursos modestos y el tema no acabó muy bien.
Ahora ha puesto su punto de mira en gente más acaudalada y cree que la mejor forma de llamar su atención es haciendo viviendas unifamiliares en parcelas lo más grandes posible. Por eso quiere dividir su terreno en el menor número de parcelas posible, para que sean cuadradas y tan grandes como se pueda, siempre que todas sean iguales y cubran el terreno completo sin dejar espacio sin utilizar.
Entrada
La entrada comienza con un número indicando cuántos casos de prueba deberán procesarse (como mucho 50.000). Cada uno está compuesto por dos números 1 ≤ w, h ≤ 109 indicando las dimensiones del terreno comprado por Moisés.
Salida
Por cada caso de prueba se indicará el mínimo número de parcelas en las que puede dividirse el terreno de Moisés de modo que todas sean iguales y cuadradas (mismo ancho que alto) y no quede ningún espacio del terreno libre.
Entrada de ejemplo
4 10 10 5 10 8 6 46349 46351
Salida de ejemplo
1 2 12 2148322499