Matcom Online Grader

Dos hermanos están ayudando a su padre en la vaquería durante el verano. Actualmente están construyendo las cercas que se usarán para dividir el campo en que las vacas van a pastar. Para seguir el método de rotación de pastos el campo se divide en potreros. Para nuestro problema vamos a interpretar el campo como una matriz de $N$ filas y $M$ columnas donde cada casilla se corresponde con un potrero. Ya los hermanos han fijado los postes y solo queda construir entre estos las cercas. El borde del campo está cercado desde el inicio, solo es necesario construir las cercas que funcionan como divisiones internas.

Para hacer más divertido el trabajo los hermanos han inventado un pequeño juego. Al inicio del juego ambos seleccionan uno de los potreros y ponen en él todos los materiales que van a necesitar. Después ambos jugadores van turnándose alternadamente hasta que no puedan hacer más movimientos. En cada turno un jugador construye una cerca horizontal o vertical entre dos cercas ya existentes usando los postes que están puestos. Siempre se debe construir la cerca de forma tal que se pueda llegar a ella desde la casilla con los materiales sin pasar por alguna cerca construida. A medida que el juego avanza se van construyendo cercas que van formando un rectángulo al rededor del potrero con los materiales. Cuando el potrero con los materiales está completamente cercado entonces no es posible hacer ninguna cerca nueva. El primer jugador que no puede hacer ningún movimiento pierde.

Los dos hermanos son muy buenos jugadores y siempre van a seguir la mejor estrategia para intentar ganar. Al inicio no se ponen de acuerdo sobre el potrero que va a contener los materiales y deciden dejarlo al azar. Aun así el hermano que juega primero decide calcular sus probabilidades de ganar. Tu tarea es sabiendo las dimensiones del campo calcular en cuantos potreros podemos poner los materiales de forma tal que gane el primer jugador.

La primera línea de la entrada consiste en un número entero $T (1 \le T \le 100)$ que indica la cantidad de casos que siguen. Cada caso es una línea con dos enteros $N$ y $M (1 \le N, M \le 10 ^ 5)$ separados por un espacio, representado la cantidad de filas y columnas en que está dividido nuestro campo.

Por cada caso se debe imprimir la cantidad de pastos que se pueden escoger para que el primer jugador tenga una estrategia que le permita ganar siempre.