相传孔明棋是三国时期孔明发明的一种益智游戏。在本题中，我们对孔明棋进行了微小的修改。游戏在一个 $(n + 2) \times (m + 2)$ 的棋盘上进行，棋盘中间的 $n \times m$ 个位置上各有一枚棋子。

孔明棋的规则如下：每次你可以选择一枚棋子，然后选择上、下、左、右四个方向之一。将该棋子沿选定方向移动一格。除上述要求外，还必须满足以下条件：起始位置和目标位置之间的中间位置必须有一枚棋子，且目标位置不能有棋子。所有位置必须在棋盘范围内。

移动后，中间位置的棋子会被移走。每次移动后，棋盘上会减少一枚棋子。现在，我们需要你解决一个问题：给定 $n$ 和 $m$，棋盘上最少能剩下多少枚棋子？

输入格式

第一行包含一个正整数 $T$ ($1 \le T \le 100$)，表示查询组数。

接下来有 $T$ 行，每行代表一个查询。每行包含两个正整数 $n$ 和 $m$ ($1 \le n, m \le 65$)。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示答案。

样例

输入格式 1

2
1 2
2 3

输出格式 1

1
2