Dazzler has a task for you.

Given two positive integers A and B, find two positive integers i and j such that:

[gcd](i,j) > 1;
A ≤ i < j ≤ B;
The value (i + j) is minimum possible.

If there are multiple solutions, you may print any of them. If no such pair exists, print -1.

------ Input Format ------ 

- First line will contain T, number of test cases. Then the test cases follow.
- Each test case contains of a single line of input, two integers A and B.

------ Output Format ------ 

For each test case, output in a single line two space-separated integers i and j satisfying all the conditions. If no such pair exists, print -1.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ A < B ≤ 10^{9}$

----- Sample Input 1 ------ 
2
2 3
2 10

----- Sample Output 1 ------ 
-1
2 4

----- explanation 1 ------ 
Test case $1$: There exists no pair satisfying all the conditions.

Test case $2$: A valid pair satisfying all the conditions is $(i, j) = (2, 4)$. The value $\texttt{gcd}(2, 4) = 2 >1$. The value $(i+j) = 6$.  
It can be proven that no such pair exists that satisfies all the conditions and has sum less than $6$.

Source: codechef | Difficulty: EASY
Tags: Number theory

Mathematics

Complete search


Solutions:
t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	if a % 2 == 0:
		if a + 2 <= b:
			print(a, a + 2)
		else:
			print(-1)
	elif a + 3 <= b:
		if a % 3 == 0:
			print(a, a + 3)
		else:
			print(a + 1, a + 3)
	else:
		print(-1)


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	if abs(a - b) == 1 or (a % 2 == 1 and abs(a - b) < 3):
		print('-1')
	elif a % 2 == 1 and a % 3 == 0:
		print(a, end=' ')
		print(a + 3)
	elif a % 2 == 0:
		print(a, end=' ')
		print(a + 2)
	else:
		print(a + 1, a + 3)


for t in range(int(input())):
	(a, b) = map(int, input().split(' '))
	num = b - a
	if num <= 1:
		print('-1')
	elif a % 2 == 0 and num >= 2:
		print(a, a + 2)
	elif a % 2 != 0 and a % 3 == 0 and (num >= 3):
		print(a, a + 3)
	elif a % 2 != 0 and b - a == 2:
		print('-1')
	elif a % 2 != 0 and b - a >= 3:
		print(a + 1, a + 3)


T = int(input())
for i in range(T):
	(A, B) = map(int, input().split())
	if A % 2 == 1 and B - A < 3:
		print(-1)
	elif A % 2 == 0 and B - A < 2:
		print(-1)
	elif A % 2 == 0:
		print(A, A + 2)
	elif A % 2 == 1 and A % 3 == 0:
		print(A, A + 3)
	else:
		print(A + 1, A + 3)


import math
T = int(input())
for _ in range(T):
	(a, b) = map(int, input().split())
	g = math.gcd(a, b)
	if a % 2 == 0:
		if a + 2 <= b:
			print(a, a + 2)
		else:
			print(-1)
	elif a % 3 == 0:
		if a + 3 <= b:
			print(a, a + 3)
		else:
			print(-1)
	elif a + 3 <= b:
		print(a + 1, a + 3)
	else:
		print(-1)


T = int(input())
count = 0
while count < T:
	(a, b) = input().split(' ')
	i = int(a)
	j = int(b)
	if j - i < 2:
		print('-1')
	elif i % 2 == 0:
		print(i, i + 2)
	elif i % 3 == 0:
		if j - i <= 2:
			print('-1')
		else:
			print(i, i + 3)
	elif j - i <= 2:
		print('-1')
	else:
		print(i + 1, i + 3)
	count = count + 1


t = int(input())
for i in range(0, t):
	(a, b) = map(int, input().split())
	if a % 2 == 0:
		x = a
		y = a + 2
	elif a % 3 == 0:
		x = a
		y = a + 3
	else:
		x = a + 1
		y = a + 3
	if y <= b:
		print(x, '', y)
	else:
		print(-1)


import math

def solve(a, b):
	if b == a + 1:
		return -1
	if a % 2:
		if b == a + 2:
			return -1
		if math.gcd(a, a + 3) > 1:
			ans = str(a) + ' ' + str(a + 3)
			return ans
		return str(a + 1) + ' ' + str(a + 3)
	else:
		return str(a) + ' ' + str(a + 2)
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	print(solve(a, b))


t = int(input())
while t:
	(a, b) = list(map(int, input().split()))
	if a % 2 == 0 and a + 2 <= b:
		print(a, a + 2)
	elif a % 3 == 0 and a + 3 <= b:
		print(a, a + 3)
	elif (a + 1) % 2 == 0 and a + 3 <= b:
		print(a + 1, a + 3)
	else:
		print('-1')
	t -= 1


T = int(input())
for tc in range(T):
	(a, b) = map(int, input().split(' '))
	if a % 2 == 0:
		if a + 2 <= b:
			print(a, a + 2)
		else:
			print(-1)
	elif a % 3 == 0:
		if a + 3 <= b:
			print(a, a + 3)
		elif a + 3 <= b:
			print(a + 1, a + 3)
		else:
			print(-1)
	elif a + 3 <= b:
		print(a + 1, a + 3)
	else:
		print(-1)


def getgcd(a, b):
	l = [0, 0]
	for i in range(a, b + 1):
		for j in range(a, i):
			if gcd(i, j) != 1:
				l[0] = i
				l[1] = j
				return l
	return l
from math import gcd
t = int(input())
for ni in range(t):
	(a, b) = map(int, input().split())
	lst = getgcd(a, b)
	b = lst
	if b[0] == 0:
		print(-1)
	else:
		print(b[1], b[0])


for _ in range(int(input())):
	(A, B) = input().split()
	A = int(A)
	B = int(B)
	if A % 2 == 0:
		if A + 2 > B:
			print(-1)
		else:
			print(A, A + 2)
	elif A % 3 == 0:
		if A + 3 > B:
			print(-1)
		else:
			print(A, A + 3)
	elif A + 3 > B:
		print(-1)
	else:
		print(A + 1, A + 3)


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	p = 0
	q = 0
	for x in range(a, b):
		if x % 2 == 0 and x + 2 <= b:
			p = x
			q = x + 2
			break
		elif x % 3 == 0 and x + 3 <= b:
			p = x
			q = x + 3
			break
	if p != 0 and q != 0:
		print(p, q)
	else:
		print(-1)


for _ in range(int(input())):
	line = input().split(' ')
	a = int(line[0])
	b = int(line[1])
	found = False
	for i in range(a, b):
		if i % 2 == 0 and i + 2 <= b:
			found = True
			print(i, i + 2)
			break
		elif i % 3 == 0 and i + 3 <= b:
			found = True
			print(i, i + 3)
			break
	if not found:
		print('-1')


for t in range(int(input())):
	(a, b) = map(int, input().split())
	c = a if a % 2 == 0 else a + 1
	import math
	if c + 2 > b:
		print(-1)
	elif math.gcd(a, c + 2) > 1:
		print(a, c + 2)
	else:
		print(c, c + 2)


import math
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	rr = a if a % 2 == 0 else a + 1
	if rr + 2 > b:
		print(-1)
	elif math.gcd(a, rr + 2) > 1:
		print(a, rr + 2)
	else:
		print(rr, rr + 2)


tst = int(input())
for i in range(tst):
	(a, b) = map(int, input().split())
	if b == a + 1:
		print(-1)
	elif a & 1:
		if b < a + 3:
			print(-1)
		elif a % 3 == 0:
			print(a, a + 3)
		else:
			print(a + 1, a + 3)
	else:
		print(a, a + 2)


t = int(input())
for i in range(t):
	w = 0
	u = 0
	(x, y) = map(int, input().split())
	if x % 2 == 0:
		w = x
		u = x + 2
	if x % 2 != 0:
		w = x + 1
		u = x + 3
		if x % 3 == 0:
			w = x
	if u <= y:
		print(w, u)
	else:
		print(-1)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	c = 0
	d = 0
	if a % 2 == 0:
		c = a
		d = a + 2
	if a % 2 != 0:
		c = a + 1
		d = a + 3
		if a % 3 == 0:
			c = a
	if d <= b:
		print(c, d)
	else:
		print('-1')


t = int(input())
while t > 0:
	(a, b) = [int(a) for a in input().split()]
	if a % 2 == 0 and b >= a + 2:
		print(str(a) + ' ' + str(a + 2))
	elif a % 3 == 0 and b >= a + 3:
		print(str(a) + ' ' + str(a + 3))
	elif a % 3 > 0 and b >= a + 3:
		print(str(a + 1) + ' ' + str(a + 3))
	else:
		print(-1)
	t -= 1


while True:
	try:
		for _ in range(int(input())):
			(a, b) = map(int, input().split())
			if a % 2 != 0:
				if b - a >= 3:
					if a % 3 == 0:
						print(a, a + 3)
					else:
						print(a + 1, a + 3)
				else:
					print(-1)
			elif b - a >= 2:
				print(a, a + 2)
			else:
				print(-1)
	except:
		break


T = int(input())
for vinay in range(T):
	flag = 0
	(A, B) = map(int, input().split())
	for kukka in range(A, B):
		if kukka % 2 == 0 and kukka + 2 <= B:
			print(kukka, kukka + 2)
			flag = 1
			break
		elif kukka % 3 == 0 and kukka + 3 <= B:
			print(kukka, kukka + 3)
			flag = 1
			break
	if flag == 0:
		print(-1)


T = int(input())
for i in range(T):
	flag = 0
	(A, B) = map(int, input().split())
	for sai in range(A, B):
		if sai % 2 == 0 and sai + 2 <= B:
			print(sai, sai + 2)
			flag = 1
			break
		elif sai % 3 == 0 and sai + 3 <= B:
			print(sai, sai + 3)
			flag = 1
			break
	if flag == 0:
		print(-1)


t = int(input())
while t > 0:
	t = t - 1
	inp = [int(x) for x in input().split(' ')]
	a = inp[0]
	b = inp[1]
	if a % 2 == 0 and b - a >= 2:
		print(a, a + 2)
	elif a % 2 != 0:
		if a != 1:
			sm = a + a * 2
			if b >= a + 3:
				ans = min(sm, 2 * a + 4)
				if ans != sm:
					if a % 3 == 0 and b >= a + 3:
						print(a, a + 3)
					else:
						print(a + 1, a + 3)
				elif b >= a * 2:
					print(a, a * 2)
				else:
					print('-1')
			else:
				print('-1')
		elif b >= a + 3:
			print(2, 4)
		else:
			print('-1')
	else:
		print('-1')


for i in range(int(input())):
	(a, b) = list(map(int, input().split()))
	diff = b - a
	if diff == 1:
		print(-1)
		continue
	if diff == 2:
		if a % 2 == 0:
			print(a, ' ', a + 2)
		else:
			print(-1)
		continue
	if a % 2 == 0:
		print(a, ' ', a + 2)
		continue
	if a % 3 == 0:
		print(a, ' ', a + 3)
		continue
	print(a + 1, ' ', a + 3)


from math import gcd
t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	if b - a == 2 and a % 2 == 1 or b - a == 1:
		print(-1)
	elif a % 2 == 0:
		print(a, a + 2)
	elif a % 3 == 0:
		print(a, a + 3)
	else:
		print(a + 1, a + 3)


import math
tests = int(input())
for i in range(tests):
	(a, b) = map(int, input().split())
	ans_a = 0
	if a % 2 == 0:
		ans_a = a
		ans_b = ans_a + 2
	else:
		for i in range(1, 4):
			temp = math.gcd(a, a + i)
			if temp > 1:
				ans_a = a
				ans_b = a + i
		if ans_a == 0:
			ans_a = a + 1
			ans_b = ans_a + 2
	if ans_a <= b and ans_b <= b:
		print(ans_a, ans_b)
	else:
		print(-1)