Problema número 755

Pelotazo urbanístico

Tiempo máximo: 1,000-2,000 sMemoria máxima: 4096 KiB
Foto a planos de viviendas

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 ≤ wh ≤ 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