Description

zhpa拥有一个n行m列的方格矩阵。行和列的编号为1到n和1到m。第a行第b列的交叉点由(a,b)表示。
最初zhpa站在左上角的(1,1)，他现在想从(1,1)这个点走向右下角(n,m)这个点。
他可以向上向下向左向右走，但是zhpa很皮，他不会往一个方向连续走两次及两次以上，并且他无法离开网格。
你是否能帮zhpa规划出一条从（1，1）走向（n，m）的路线，并且这条路线要尽可能的短，如果可以，输出最短步数，如果不行输出-1

Format

Input

输入一个正整数T，表示有T组案例。（ 1 ≤ T ≤ 1e3 ）
接下来有T行。每行有两个数分别表示n和m，n和m之间有空格。( 1≤ n,m ≤ 1e9 )

Output

对于每组案例，如果不可能在给定的条件下达到（n,m）这个点就打印-1，否则打印最小的移动次数，然后换行。

Sample 1

Input

6
1 1
2 1
1 3
4 2
4 6
10 5

Output

0
1
-1
6
10
17

Limitation

1s,125MB

Source

每日一题