Mirko 想买一块地来为他的家人盖一栋房子。到目前为止，他已经看了 $K$ 块地。每块地都是矩形的，我们可以将其看作一个有 $N$ 行 $M$ 列的矩阵，总共有 $N \times M$ 个格子。

Mirko 知道，在开始建造之前，这片土地需要定期维护，草坪也需要修剪。因此，Mirko 买了一台除草机。为了修剪完这片 $N$ 行 $M$ 列的整片草坪，他需要经过每个格子至少一次。他可以从任意一个格子开始，并朝向四个基本方向（上、下、左、右）之一。他的除草机只能向前移动（移动到当前朝向的相邻格子）或进行 90 度转弯。此外，为了自身安全，Mirko 只能在自己的土地上使用除草机，因此他不能离开矩阵。

由于让除草机转弯并不容易，Mirko 希望以最少的转弯次数来修剪完草坪。对于他目前看过的每块地，Mirko 都想知道在修剪完整个草坪的情况下，他最少需要转弯多少次。请帮助 Mirko 解决这个问题。

输入格式

输入的第一行包含一个正整数 $K$ ($1 \le K \le 50\,000$)，表示土地的数量。

接下来的 $K$ 行，每行包含两个正整数 $N$ 和 $M$ ($1 \le N, M \le 1\,000\,000$)，表示每块土地的行数和列数。

输出格式

对于 Mirko 看过的每块土地，在单独的一行中输出修剪完整个草坪所需的最少转弯次数。

子任务

在占总分 50% 的测试数据中，Mirko 只会看一块土地（即 $K = 1$），且这块土地的尺寸将小于 500（即 $N, M < 500$）。

样例

输入样例 1

2
1 10
10 1

输出样例 1

0
0

输入样例 2

3
1 1
3 3
3 4

输出样例 2

0
4
4

输入样例 3

2
5 8
6 4

输出样例 3

8
6

说明

样例 1 解释：

第一块土地可以在不进行任何转弯的情况下修剪完毕：只需从表格第一列的格子开始，朝向右侧并一直向前移动即可。第二块土地同理。