Dzidzio and meeting with fans

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

After a concert in an extremely strange country, Dzidzio decided to give a few autographs to his ardent fans. He had recently been thinking about a new logo for his band (see Notes), so he decided that his autograph would consist only of new logos. For a fan to get maximum pleasure from the autograph, the following strange conditions must be met:

1. The autograph is a grid of size \(n\) by \(m\).

2. Each cell must contain exactly one logo.

3. The number of points where only one arrow of the logo ends must be minimal.

Dzidzio figured out the first two conditions immediately, and he turned to you for the third one. Write a program to help him calculate the minimum possible number of such points. The size of the logo is 1 by 1. The logo can be rotated by 90, 180, and 270 degrees.

Input

The first line contains a single integer \(t\) — the number of fans.

The next \(t\) lines each contain two integers \(n_i, m_i\) — the dimensions of the autograph that the \(i\)-th fan wants.

Output

For each fan, output in a separate line the minimum possible number of points where exactly one arrow ends.

Constraints

\(1 \le t \le 100\),

35% of tests: \(1 \le n_i, m_i \le 10^3\),

65% of tests: \(1 \le n_i, m_i \le 10^9\).

Samples

Input (stdin) сopy	Output (stdout) сopy
3 1 1 1 2 4 3	3 2 0

Notes