Description

给定一个n*m的矩阵，每次你可以选择前进一格或转弯（90度）， 求在不出这个矩阵的情况下遍历全部格点所需最少转弯次数。 有多组数据

Format

Input

第一行给出数字组数据 对于每组数据 每一行包含两个正整数N和M(1 ≤ N, M ≤ 1 000 000), 分别表示每大块土地可以看成N× M小块

Output

对于每一大块土地，输出修剪草坪需要的最少转弯次数

Samples

1
5 8

8

3
1 1
3 3
3 4

0
4
4

Limitation

1s, 1024KiB for each test case.