2137C.md (1143B)
1 Source: https://codeforces.com/problemset/problem/2137/C 2 3 C. Maximum Even Sum 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given two integers $a$ and $b$. You are to perform the following procedure: 22 23 First, you choose an integer $k$ such that $b$ is divisible by $k$. Then, you simultaneously multiply $a$ by $k$ and divide $b$ by $k$. 24 25 Find the greatest possible even value of $a+b$. If it is impossible to make $a+b$ even, output $-1$ instead. 26 27 Input 28 29 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 30 31 The first line of each test case contains two integers $a$ and $b$ ($1 \leq a,b \leq a\cdot b \leq 10^{18})$. 32 33 Output 34 35 For each test case, output the maximum even value of $a+b$ on a new line. 36 37 Example 38 39 Input 40 41 ``` 42 7 43 44 8 1 45 46 1 8 47 48 7 7 49 50 2 6 51 52 9 16 53 54 1 6 55 56 4 6 57 ``` 58 59 Output 60 61 ``` 62 -1 63 6 64 50 65 8 66 74 67 -1 68 14 69 ``` 70 71 Note 72 73 In the first test case, it can be shown it is impossible for $a+b$ to be even. 74 75 In the second test case, the optimal $k$ is $2$. The sum is $2+4=6$.