beecrowd | 1028

Tarjetas Coleccionables

Por Neilor Tonin, URI Brazil

Timelimit: 1

A Ricardo y Vicente les encantan las tarjetas de fútbol coleccionables. En su tiempo libre, organizan una forma de jugar algún juego que involucre a dichas tarjetas. Ambos también tienen el hábito de intercambiar las tarjetas repetidas con sus amigos, y un día pensaron en un juego diferente. Llamaron a todos sus amigos y propusieron lo siguiente: con las tarjetas en mano, cada uno intenta hacer un intercambio con su amigo más cercano siguiendo esta sencilla regla: cada uno debe contar cuántas tarjetas tiene. Después de esto, tienen que dividirlas en pilas de igual tamaño, tan grande como sea posible para ambos jugadores. Luego, cada uno elige una de las pilas de tarjetas de su amigo para recibir. Por ejemplo, si Ricardo y Vicente intercambiaran tarjetas, teniendo respectivamente 8 y 12 cada uno, ambos deben poner sus tarjetas en pilas de cuatro (Ricardo tendría dos pilas y Vicente tres), y ambos eligen una pila del otro para recibir.

Entrada

La primera línea de entrada contiene un solo entero N (1 ≤ N ≤ 3000), indicando el número de casos de prueba. Cada caso de prueba contiene dos números enteros F1 (1 ≤ F1 ≤ 1000) y F2 (1 ≤ F2 ≤ 1000)  indicando, respectivamente, la cantidad de tarjetas coleccionables que Ricardo y Vicente tienen para intercambiar.

Salida

Para cada caso de prueba habrá un número entero en la salida, que representa el tamaño máximo de la pila de tarjetas que se pueden intercambiar entre dos jugadores.

Ejemplo de entrada Ejemplo de salida

3
8 12
9 27
259 111

4
9
37