Por Neilor Tonin, URI Brazil
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.
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.
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 |
4 |