310694: CF1872C. Non-coprime Split
Description
You are given two integers $l \le r$. You need to find positive integers $a$ and $b$ such that the following conditions are simultaneously satisfied:
- $l \le a + b \le r$
- $\gcd(a, b) \neq 1$
or report that they do not exist.
$\gcd(a, b)$ denotes the greatest common divisor of numbers $a$ and $b$. For example, $\gcd(6, 9) = 3$, $\gcd(8, 9) = 1$, $\gcd(4, 2) = 2$.
InputThe first line of the input contains an integer $t$ ($1 \le t \le 500$) — the number of test cases.
Then the descriptions of the test cases follow.
The only line of the description of each test case contains $2$ integers $l, r$ ($1 \le l \le r \le 10^7$).
OutputFor each test case, output the integers $a, b$ that satisfy all the conditions on a separate line. If there is no answer, instead output a single number $-1$.
If there are multiple answers, you can output any of them.
ExampleInput11 11 15 1 3 18 19 41 43 777 777 8000000 10000000 2000 2023 1791791 1791791 1 4 2 3 9840769 9840769Output
6 9 -1 14 4 36 6 111 666 4000000 5000000 2009 7 -1 2 2 -1 6274 9834495Note
In the first test case, $11 \le 6 + 9 \le 15$, $\gcd(6, 9) = 3$, and all conditions are satisfied. Note that this is not the only possible answer, for example, $\{4, 10\}, \{5, 10\}, \{6, 6\}$ are also valid answers for this test case.
In the second test case, the only pairs $\{a, b\}$ that satisfy the condition $1 \le a + b \le 3$ are $\{1, 1\}, \{1, 2\}, \{2, 1\}$, but in each of these pairs $\gcd(a, b)$ equals $1$, so there is no answer.
In the third sample test, $\gcd(14, 4) = 2$.
Output
给定两个整数 \( l \le r \),需要找到两个正整数 \( a \) 和 \( b \),使得以下条件同时满足:
1. \( l \le a + b \le r \)
2. \( \gcd(a, b) \neq 1 \)
如果没有这样的 \( a \) 和 \( b \) 存在,则报告不存在。\( \gcd(a, b) \) 表示 \( a \) 和 \( b \) 的最大公约数。例如,\( \gcd(6, 9) = 3 \),\( \gcd(8, 9) = 1 \),\( \gcd(4, 2) = 2 \)。
输入数据格式:
输入的第一行包含一个整数 \( t \)(\( 1 \le t \le 500 \))——测试用例的数量。
然后是 \( t \) 个测试用例的描述。
每个测试用例的描述只有一行,包含两个整数 \( l, r \)(\( 1 \le l \le r \le 10^7 \))。
输出数据格式:
对于每个测试用例,输出满足所有条件的整数 \( a, b \)(如果存在多个答案,可以输出其中任意一个)。如果没有答案,则输出一个数字 \( -1 \)。题目大意:非互质拆分 给定两个整数 \( l \le r \),需要找到两个正整数 \( a \) 和 \( b \),使得以下条件同时满足: 1. \( l \le a + b \le r \) 2. \( \gcd(a, b) \neq 1 \) 如果没有这样的 \( a \) 和 \( b \) 存在,则报告不存在。\( \gcd(a, b) \) 表示 \( a \) 和 \( b \) 的最大公约数。例如,\( \gcd(6, 9) = 3 \),\( \gcd(8, 9) = 1 \),\( \gcd(4, 2) = 2 \)。 输入数据格式: 输入的第一行包含一个整数 \( t \)(\( 1 \le t \le 500 \))——测试用例的数量。 然后是 \( t \) 个测试用例的描述。 每个测试用例的描述只有一行,包含两个整数 \( l, r \)(\( 1 \le l \le r \le 10^7 \))。 输出数据格式: 对于每个测试用例,输出满足所有条件的整数 \( a, b \)(如果存在多个答案,可以输出其中任意一个)。如果没有答案,则输出一个数字 \( -1 \)。