题目描述

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

1. 选择一个整数 $k$，使得 $b$ 能被 $k$ 整除（即 $k$ 是 $b$ 的约数）。
2. 同时将 $a$ 乘以 $k$，并将 $b$ 除以 $k$。

请找出 $a + b$ 可能的最大偶数值。若无法使 $a + b$ 为偶数，则输出 $-1$。

输入格式

每组测试包含多组测试用例。第一行输入测试用例数量 $t$（$1 \leq t \leq 10^4$），随后依次描述每组测试用例。

每组测试用例的输入格式如下：

• 一行包含两个整数 $a$ 和 $b$（$1 \leq a,b \leq a \cdot b \leq 10^{18}$）。

输出格式

对于每组测试用例，在新的一行输出 $a + b$ 可能的最大偶数值。若无法使 $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$。此时 $a$ 变为 $1 \times 2 = 2$，$b$ 变为 $8 \div 2 = 4$，和为 $2 + 4 = 6$。

来源

Codeforces 2137C，英文题名 Maximum Even Sum。