En un juego no muy común de dominó se pueden crear diferentes reglas. Se le da una tabla rectangular de M × N cuadrados. También se le da un número ilimitado de piezas de dominó de tamaño estándar 2 × 1 (plazas). Se le permite girar las piezas del tal manera que debe colocar tantas piezas de dominó como sea posible en el tablero dado de manera que se cumplan las siguientes condiciones:

1. Cada dominó cubre completamente dos cuadrados (plazas).

2. No hay dos piezas de dominó que se superponen.

3. Cada dominó encuentra en su totalidad dentro del tablero. Está permitido tocar los bordes del tablero.

Tarea de hoy! Encuentra el número máximo de piezas de dominó, que pueden ser colocados en el tablero bajo estas restricciones.

Input

La primera línea del INPUT comienza con un número M que indica el número de casos del problema propuesto. (1 ≤ M ≤ 100)

Cada caso está compuesto de la(s) siguiente(s) linea(s):

En una sola línea te dan dos números enteros M y N - tamaños del tablero y las piezas de dominó respectivamente ( 1 ≤ M ≤ N ≤ 16 ).

Output

Salida de un número - el número máximo de fichas de dominó que pueden ser colocadas.

Entrada de ejemplo