给你一个 n × m 的方格，初始时所有方格都是红色。

    现在你可以将矩形块沿网格线切割成两个新的矩形块，你可以做这个操作任意多次，

    但是不能切割成 1 × 1 的矩形块。最后得到一个矩形组，我们希望任意一对相邻的

    单元格（同一个矩形块中）都具有不同的颜色，你可以把任意 1 × 1 的方格染成蓝色，

    输出最小需要将多少个 1 × 1 的方格涂成蓝色。

    第一行输入一个整数 T ，表示有 T 个测试样例。（1 ≤ T ≤ 1000）

    第二行输入两个整数 n ， m，表示方格大小（1 ≤ n , m ≤ 30000 ， n × m ≥ 2）

    输出一个整数表示最小涂色次数使任意两个相邻方格不同色