Please forgive us, we could'nt come up with any story.Just solve this Boring Question to get 100 points :).

There is a N X M array of switches controlling N X M matrix of bulbs .

Initially, all the bulbs are in OFF state, You just have to turn all the bulbs ON, but there is a defect in the switch system.

If any one of the switches is toggled(OFF to ON and vice versa) all the switches of adjacent bulbs also gets toggled(including the bulbs which are diagonal to it) thereby turning them ON/OFF also

So, it becomes an easy task now, tell us the number of minimum toggles required to turn all the bulbs ON.

Input :

First Line of each test case tells the total number of cases T. The next T lines gives the value of N X M

Output:

Print the minimum number of toggels required to turn all the lights ON. Changing line after every Case.

Constraints:

1 <= T <= 1000000

0<= N <= 10^9

0<= M <= 10^9