题目描述

相传，孔明棋是三国时期孔明发明的一种智力游戏。在这个问题中，我们对孔明棋做了一个小小的修改。游戏在一个 $(n+2)×(m+2)$ 的棋盘上进行，在棋盘中间的 $n×m$ 位置上每个位置都有一个棋子。

孔明棋的规则如下:每次你可以选择一个棋子，然后在四个方向中选择一个: 上、下、左、右。将棋子从原来的位置向选定的方向移动一个格。除上述要求外，还必须满足以下条件:在原位置和目标位置之间的中间位置上必须有棋子，目标位置上不得有棋子。所有的位置都必须在棋盘上。

移动后，中间位置的棋子被拿走。每走一步棋，就会从棋盘上移走一个棋子。现在，我们需要你解决一个问题:给定 $n$ 和$m$，棋盘上剩下的最小棋子数是多少?

输出

第一行包含一个正整数$T$，其中 $1≤T≤1000$，表示查询集的个数。

接下来，将有T行，每一行表示一个查询。每行包含两个正整数$n$和$m$，其中$1≤n,m≤65$。

输出

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

样例

2
1 2
2 3

1
2

样例解释

对于第二组数据，$n = 2$, $m = 3$, 可以证明没有办法能通过若干次移动后剩下的棋子小于 $2$ 个。 其中一种移动方法如图所示。（红色为棋子所在位置，白色为空位置）