← 返回题目列表

Codeforces · 1872/C

C. 非互质分裂

中文机器翻译题面 查看原题

给你两个整数 $$$l \le r$$$。您需要找到正整数 $$$a$$$ 和 $$$b$$$ 以便同时满足以下条件:

- $$$l \le a + b \le r$$$
- $$$\gcd(a, b) \neq 1$$$

或报告它们不存在。

$$$\gcd(a, b)$$$ 表示数字 $$$a$$$ 和 $$$b$$$ 的最大公约数。例如,$$$\gcd(6, 9) = 3$$$、$$$\gcd(8, 9) = 1$$$、$$$\gcd(4, 2) = 2$$$。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 500$$$) — 测试用例的数量。

然后是测试用例的描述。

每个测试用例的描述中唯一的一行包含 $$$2$$$ 整数 $$$l, r$$$ ($$$1 \le l \le r \le 10^7$$$)。

输出

对于每个测试用例,在单独的行上输出满足所有条件的整数 $$$a, b$$$。如果没有答案,则输出单个数字$$$-1$$$。

如果有多个答案,则可以输出其中任何一个。

示例

输入 #1

11
11 15
1 3
18 19
41 43
777 777
8000000 10000000
2000 2023
1791791 1791791
1 4
2 3
9840769 9840769

输出 #1

6 9
-1
14 4
36 6
111 666
4000000 5000000 
2009 7
-1
2 2
-1
6274 9834495

注意

在第一个测试用例中,$$$11 \le 6 + 9 \le 15$$$, $$$\gcd(6, 9) = 3$$$,并且满足所有条件。请注意,这不是唯一可能的答案,例如,$$$\{4, 10\}、\{5, 10\}、\{6, 6\}$$$ 也是此测试用例的有效答案。

在第二个测试用例中,满足条件 $$$1 \le a + b \le 3$$$ 的唯一对 $$$\{1, 1\}, \{1, 2\}, \{2, 1\}$$$,但在每个对中 $$$\gcd(a, b)$$$ 等于 $$$1$$$,所以没有答案。

在第三个示例测试中,$$$\gcd(14, 4) = 2$$$。