Problem Description

According to legend, Kongming Chess is an intellectual game invented by Kongming during the Three Kingdoms period. In this problem, we make a slight modification to Kongming Chess. The game is played on an $(n+2) \times (m+2)$ chessboard, and there is one chess piece on each of the $n \times m$ positions in the middle of the chessboard.

The rules of Kongming Chess are as follows: Each time, you can choose one chess piece and then choose one of the four directions: up, down, left, or right. Move the chess piece one grid away in the chosen direction from its original position. In addition to the above requirement, the following conditions must be satisfied: There must be a chess piece on the intermediate position between the original position and the target position, and the target position must not have a chess piece. All positions must be on the chessboard.

After the move, the chess piece on the intermediate position is taken away. After each move, one chess piece will be removed from the chessboard. Now, we need you to solve a problem: Given n and m, what is the minimum number of chess pieces left on the chessboard?

Input

The first line contains a positive integer, $T$, where $1 ≤ T ≤ 100$, representing the number of query sets.

Next, there will be T lines, each representing a query. Each line contains two positive integers, $n$ and $m$, where $1 ≤ n, m ≤ 65$.

Output

For each test case, output one line containing an integer representing the answer.

2
1 2
2 3

1
2