题目描述

给定两个整数 $a$ 和 $b$。你需要执行如下操作：

首先，选择一个整数 $k$，满足 $b$ 能被 $k$ 整除（即 $b \bmod k = 0$）。 然后，同时执行两个操作：将 $a$ 乘以 $k$，将 $b$ 除以 $k$。

请你求出操作后 $a + b$ 的最大可能偶数值。 如果无法让 $a + b$ 成为偶数，则输出 $-1$。

输入格式

每个测试包含多组数据。 第一行输入测试用例数 $t$（$1 \le t \le 10^4$）。

每组测试用例的描述如下： 第一行包含两个整数 $a$ 和 $b$（$1 \le a,b \le a \cdot b \le 10^{18}$）。

输出格式

对于每组测试用例，在新的一行输出 $a+b$ 的最大偶数值；若无法得到偶数，输出 $-1$。

样例输入

7
8 1
1 8
7 7
2 6
9 16
1 6
4 6

样例输出

-1
6
50
8
74
-1
14

样例说明

• 第一个测试用例：可以证明无法使 $a+b$ 为偶数，因此输出 $-1$。
• 第二个测试用例：最优选择 $k=2$，操作后和为 $2+4=6$。