#YS260744. 不要互质

不要互质

题目描述

给定两个整数llrr,你需要找到正整数aabb,使得a,ba,b满足以下要求:

  • la+brl \le a+b \le r
  • gcd(a,b)1\gcd(a,b) \ne 1

或者反馈不存在。

其中,gcd(a,b)\gcd(a,b)表示a和b的最大公约数,例如gcd(6,9)=3,gcd(9,14)=1\gcd(6,9)=3,\gcd(9,14)=1

你需要回答 tt 个独立的测试用例。

输入格式

输入的第一行包含一个整数 tt (1t5001 \le t \le 500),表示测试用例的数量。接下来 tt 组测试用例依次给出。

对于每个测试用例,均给出一行,包含两个数字l,rl,r (1lr107)(1 \le l \le r \le 10^7)

输出格式

对于每个测试用例,输出一对符合要求的a,ba,b,若这样的数字不存在则输出-1

如果有多个满足要求的a,ba,b,输出任意一组即可。

样例

11
11 15
1 3
18 19
41 43
777 777
8000000 10000000
2000 2023
1791791 1791791
1 4
2 3
9840769 9840769
6 9
-1
14 4
36 6
111 666
4000000 5000000 
2009 7
-1
2 2
-1
6274 9834495

数据范围与提示

对于25%数据,r100r \leq 100

对于50%数据,r10000r \leq 10000

对于100%数据,1t500; 1lr1071 \leq t \leq 500;\ 1 \leq l \le r \leq 10^7