题目描述

给定由 $n \times m$ 个方格组成的棋盘。请你从棋盘中选择某个方格作为起点，然后向相邻（上下左右）的一个方格行走，再向相邻的一个方格行走……

你的目标是走遍棋盘的所有方格，换言之每个方格至少被你走过一次，但在过程中不可以走出棋盘。

请问，如何设计行走路线，可以使路线上的转折点（原先横着走变成竖着走，或者原先竖着走变成横着走）尽可能少？

例如上图展示了 $6 \times 4$ 棋盘的两种路线，左边的路线有 $7$ 个转折点，右边的路线有 $6$ 个转折点。因此右边的路线优于左边的。可以证明，没有比 $6$ 个转折点更优的路线。

输入格式

第一行一个正整数 $T$，表示数据组数，

接下来 $T$ 行，每行两个整数 $n,m$，表示一个棋盘。

输出格式

$T$ 行，每行一个整数，表示答案。

样例输入输出

3
6 4
5 8
1 10

6
8
0

说明/提示

对于 $100\%$ 的数据，保证 $1 \leq T ≤ 10^6$，$1 \leq n,m \leq 10^6$。