El monstruo del lago ness es un animal no identificado misterioso, dicen que habita en el lago Ness, un gran lago ubicado en la ciudad de Inverness al norte de Escocia.

En Julio de 2003, la red BBC hizo un a gran investigación sobre el lago Ness, usando 600 sonares separados.

Ningún vestigio de monstruo marino alguno fue encontrado.

El equipo de la BBC concluyó que Nessie no existe; ahora, queremos repetir el experimento.

Dada una grilla de n filas y m columnas, representando el lago (6 <= n, m <= 10000), encuentre el menor número de sonares que necesitarás colocar en el lago, de tal forma que podamos controlar todas las posiciones de la matriz.

Se tienen las siguientes condiciones:

• Un sonar ocupa una posición de la grilla, además de su propia posición, el sonar controla todas sus posiciones adyacentes.
• Las posiciones de los bordes de la grilla no necesitan ser controladas, ya que Nessie no se podría esconder en ellas (Es demasiado grande para caber).

Considere las siguientes figuras:

En las figuras, x representa un sonar, y las posiciones oscuras representan las posiciones controladas por sonares. La última figura ejempliica una solución para el problema.

La primera línea de entrenada contiene un entero t, indicando el número de casos de prueba. cada caso de prueba está descrito por una línea conteniendo dos enteros separados por un espacio, n y m, indicando el tamaño de la grilla (n filas y m colúmnas).

Para cada caso de prueba, imprima una línea conteniendo el menor número de sonares necesarios.