Chef has two numbers N and M. He calls a pair of numbers (A, B) *good* if it satisfies the following conditions:
1 ≤ A, B ≤ M
\gcd(A, B) ≥ N

Chef wants to find a good pair (A, B) such that the value of |A - B| is maximized. Can you help Chef? (Here |X| represents the absolute value of X).

If there are multiple good pairs for which the value of |A - B| is maximized, you can print any of them. It can be proved that under the given constraints, at least one good pair always exists.

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

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first line of each test case contains two integers N and M — the parameters mentioned in the statment.

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

For each test case, output two integers A and B such that (A, B) is a good pair and the value of |A - B| is maximized.

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

$1 ≤ T ≤ 1000$
$1 ≤ N ≤ 10^{5}$
$N ≤M ≤10^{9}$
- Sum of $N$ over all test cases does not exceed $2 \cdot 10^{5}$

----- Sample Input 1 ------ 
3
5 6
2 8
10 89
----- Sample Output 1 ------ 
6 6
8 2
11 88

----- explanation 1 ------ 
Test case $1$: $(5, 5)$ and $(6, 6)$ are the only good pairs and for both of them the value of $|A - B|$ is $0$.

Test case $2$: $(6, 8), (8, 6), (2, 8), (8, 2), (4, 6), (6, 4), (2, 6), (6, 2), (2, 4), (4, 2)$ and $(2, 2)$ are the good pairs out of which $|A - B|$ is maximum for $(2, 8)$ and $(8, 2)$.

Difficulty: MEDIUM
Tags: Number theory

Mathematics

Starter code:

Solutions:
t = int(input())
for _ in range(t):
	(x, y) = map(int, input().split())
	f = y - y % x - x
	num = [x, x * (y // x)]
	for i in range(x + 1, min(y + 1, x * 2)):
		if y - y % i - i >= f:
			f = y - y % i - i
			num = [i, i * (y // i)]
			continue
	print(*num)


T = int(input())
for i in range(T):
	(A, B) = map(int, input().split())
	c = 0
	(c1, c2) = (0, 0)
	for j in range(A, min(A + A, B) + 1):
		ans = B - B % j
		if ans - j >= c:
			c = ans - j
			(c1, c2) = (j, ans)
	print(c1, c2)


T = int(input())
for i in range(T):
	(n, m) = map(int, input().split())
	ans = 0
	muns = [0, 0]
	for b in range(n, min(m + 1, 2 * n)):
		k = b * (m // b)
		if k - b >= ans:
			ans = k - b
			nums = [k, b]
	print(nums[1], nums[0])


for case in range(int(input())):
	(n, m) = map(int, input().split())
	ans = 0
	nums = [0, 0]
	for a in range(n, min(m + 1, 2 * n)):
		k = a * (m // a)
		if k - a >= ans:
			ans = k - a
			nums = [k, a]
	print(nums[1], nums[0])


try:
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		if m < 2 * n:
			print(m, m)
		elif m >= 2 * n and m % n == 0:
			print(m, n)
		else:
			res = 0
			res_2 = 0
			div = m // 2
			if m >= 2 * n:
				div = 2 * n
			Min = 0
			for i in range(n, div):
				d = m // i
				c_Min = i * d - i
				if c_Min > Min:
					res = i
					res_2 = i * d
					Min = c_Min
			print(res, res_2)
except:
	pass


from math import gcd
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	maxd = 0
	(ca, cb) = (0, 0)
	for i in range(a, min(a + a, b) + 1):
		result = b - b % i
		if result - i >= maxd:
			maxd = result - i
			(ca, cb) = (i, result)
	print(ca, cb)


import math
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	d = 0
	A = 0
	B = 0
	for i in range(min(M - N + 1, N + 1)):
		a = N + i
		b = M // (N + i) * (N + i)
		if b - a >= d:
			d = b - a
			A = a
			B = b
	print(A, B)


for _ in range(int(input())):
	(n, m) = map(int, input().split(' '))
	max = [0, 0, 0]
	for i in range(min(n, m - n + 1)):
		a = n + i
		b = (n + i) * (m // (n + i))
		if max[0] <= b - a:
			max = [b - a, a, b]
	print(max[1], max[2])


def solve(N, M):
	res = None
	max_diff = 0
	for a in range(N, min(2 * N, M + 1)):
		r = M % a
		b = M - r
		d = abs(b - a)
		if d >= max_diff:
			max_diff = d
			res = (a, b)
	return res
t = int(input())
for ti in range(t):
	(N, M) = map(int, input().split())
	res = solve(N, M)
	print(*res)


def hcf(a, b):
	if b == 0:
		return a
	else:
		return hcf(b, a % b)

def sol2(n, m):
	l = m / 2
	if m >= n * 2:
		l = n * 2
	s = 0
	for i in range(n, l):
		y = m // i
		e = i * y - i
		if e > s:
			p = i
			t = i * y
			s = e
	return (p, t)

def sol(n, m):
	if m < 2 * n:
		return (m, m)
	elif m % n == 0:
		return (m, n)
	else:
		return sol2(n, m)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(anya, boruto) = sol(n, m)
	print(str(anya) + ' ' + str(boruto))


def sol2(kawaii, anya):
	loid = kawaii * 2
	syon_boy = 0
	for i in range(kawaii, loid):
		yor = anya // i
		elegance = i * yor - i
		if elegance > syon_boy:
			penguin = i
			tennis = i * yor
			syon_boy = elegance
	return (penguin, tennis)

def sol(naruto, manga):
	if manga < 2 * naruto:
		return (manga, manga)
	elif manga % naruto == 0:
		return (manga, naruto)
	else:
		return sol2(naruto, manga)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(anya, boruto) = sol(n, m)
	print(str(anya) + ' ' + str(boruto))


def gcd(n, m):
	result = min(n, m)
	while result:
		if n % result == 0 and m % result == 0:
			break
		result -= 1
	return result

def sol2(kawaii, anya):
	loid = anya / 2
	if anya >= kawaii * 2:
		loid = kawaii * 2
	syon_boy = 0
	for i in range(kawaii, loid):
		yor = anya // i
		elegance = i * yor - i
		if elegance > syon_boy:
			penguin = i
			tennis = i * yor
			syon_boy = elegance
	return (penguin, tennis)

def sol(naruto, manga):
	if manga < 2 * naruto:
		return (manga, manga)
	elif manga % naruto == 0:
		return (manga, naruto)
	else:
		return sol2(naruto, manga)
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	(anya, boruto) = sol(n, m)
	print(str(anya) + ' ' + str(boruto))


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = -1
	b = -1
	ans = 0
	for i in range(n, min(m + 1, 2 * n + 1)):
		x = i
		y = m // i * i
		if abs(x - y) >= ans and x <= m and (y <= m):
			a = x
			b = y
			ans = abs(a - b)
	print(a, b)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	ma = 0
	answ = 0
	ansx = 0
	loopbreak = x * 2
	while x <= loopbreak:
		temp = y // x
		te = temp * x
		check = te - x
		if ma < check:
			ma = check
			answ = x
			ansx = te
		x += 1
	if ma == 0:
		print(y, y)
		continue
	print(answ, ansx)


import math
t = int(input())
while t > 0:
	tmp = input().split()
	tmp = [int(x) for x in tmp]
	arr = []
	l = min(2 * tmp[0], tmp[1])
	for i in range(tmp[0], l + 1):
		a = i
		b = tmp[1] - tmp[1] % i
		if math.gcd(a, b) >= tmp[0]:
			arr.append({'a': a, 'b': b})
	p = {'a': 0, 'b': 0}
	for x in arr:
		if abs(x['b'] - x['a']) >= abs(p['b'] - p['a']):
			p = x
	print(p['a'], p['b'])
	t -= 1