B. 超平坦棋盘
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

雪碧喜欢玩 Minecraft 和国际象棋，这天他建立了一个超平坦的棋盘世界，世界是一个无尽大小的国际象棋棋盘，其中在最初棋盘上的所有格子都有一只马。棋盘本身是一个无穷大的二维矩阵，每个格子都有一个相应的整数坐标，可以为负。

这天，游戏触发了一个奖励事件。在事件中，位于棋盘坐标 $$$(n, m)$$$ 的马被移除了，留下了一个空格。同时，位于棋盘坐标 $$$(0, 0)$$$ 的马被升级成为了超级马，奖励事件的目标是将超级马移动到 $$$(n, m)$$$ 的位置。

雪碧可以移动任意种类的马，但要求过程中任意类型的马都不能同时在同一个格子中，并且移动任何马的次数之和最小。

可怜的雪碧不知道如何移动这些马来达成目标，所以他决定请教你，最少需要移动多少次才能完成这个目标。

马的移动规则是：如果马位于 $$$(x, y)$$$ 的位置，那么它可以移动到 $$$(x \pm 1, y \pm 2)$$$ 或 $$$(x \pm 2, y \pm 1)$$$ 的位置，当且仅当目标位置上没有其他马。

Input

第一行包含一个整数 $$$T$$$ ($$$1 \le T \le 100$$$)，表示测试用例数。

接下来 $$$T$$$ 行，每行包含两个整数 $$$n, m$$$ ($$$1 \le n, m \le 10^5$$$, $$$n \cdot m \le 10^5$$$)，表示目标位置的坐标。

保证所有测试用例的 $$$n \cdot m$$$ 之和不大于 $$$10^5$$$。

Output

对于每个测试用例，输出一行一个整数，表示最少需要移动的次数。

Example
Input
5
3 3
4 4
5 5
6 6
7 7
Output
5
13
15
13
21
Note

对于第一组样例：

初始时，只有 $$$(3, 3)$$$ 为空第一步：$$$(1, 2) \to (3, 3)$$$第二步：$$$(0, 0) \to (1, 2)$$$
第三步：$$$(2, 1) \to (0, 0)$$$第四步：$$$(3, 3) \to (2, 1)$$$第五步：$$$(1, 2) \to (3, 3)$$$

可以证明，不存在更优方案。