Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese], and [Bengali] as well.

You are given two integers $L$ and $R$. Find the smallest non-negative integer $N$ such that
$$N \,\%\, L > N \,\%\, (L + 1) > \ldots > N \,\%\, (R - 1) > N \,\%\, R \,.$$

Here, $\%$ is the modulo operator, so $A \,\%\, B$ is the remainder of $A$ after division by $B$. For example, $11 \,\%\, 3 = 2$.

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first and only line of each test case contains two space-separated integers $L$ and $R$.

------  Output ------
For each test case, print a single line containing one integer ― the smallest possible $N$, or $-1$ if no solution exists.

It is guaranteed that when a solution exists, the smallest solution does not exceed $10^{18}$.

------  Constraints ------
$1 ≤ T ≤ 10^{5}$
$1 ≤ L < R ≤ 10^{6}$

----- Sample Input 1 ------ 
2

4 6

1 2
----- Sample Output 1 ------ 
6

-1
----- explanation 1 ------ 
Example case 1: $N = 6$ satisfies the given condition, since $6 \,\%\, 4 \,(= 2) > 6 \,\%\, 5 \,(= 1) > 6 \,\%\, 6 \,(= 0)$. Notice that $N = 7$ also satisfies the condition, but it is larger.

Example case 2: It is impossible to find a valid solution because for any non-negative integer $N$, we have $N \,\%\, 1 \,(= 0) ≤ N \,\%\, 2$.

Difficulty: MEDIUM
Tags: Mathematics

Starter code:

Solutions:
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	if r < l * 2:
		print(r)
	else:
		print(-1)


x = int(input())
g = []
for hh in range(0, x):
	t = str(input())
	up = t.split(' ')
	iir = []
	for bb in up:
		iir.append(int(bb))
	g.append(iir)
for nnv in g:
	a = nnv[0]
	b = nnv[1]
	if a == 1 or b == 1 or b % a == 0:
		print(-1)
	elif b - a == 1:
		print(b)
	else:
		ab = b - a + 1
		if a >= ab:
			print(b)
		else:
			print(-1)


for i in range(int(input())):
	(l, r) = list(map(int, input().split()))
	if l <= r // 2:
		print('-1')
	else:
		print(r)


for _ in range(int(input())):
	(a, b) = map(int, input().split())
	if a <= b // 2:
		print(-1)
	else:
		print(b)


import math
for tc in range(int(input())):
	(l, r) = map(int, input().split())
	d = r - l
	if d >= l:
		print(-1)
	else:
		print(r)


T = int(input())
for i in range(T):
	(L, R) = map(int, input().split())
	if L * 2 > R:
		print(R)
	else:
		print(-1)


for _ in range(int(input())):
	(x, y) = map(int, input().split())
	print(y) if y - x < x else print(-1)


from math import sqrt, ceil, floor, gcd, log2
import sys
from sys import stdin, stdout
from collections import Counter, defaultdict, OrderedDict, deque
from itertools import combinations, groupby
from time import time
from heapq import heappop, heappush, heapify
t = int(input())
for _ in range(t):
	(l, r) = map(int, input().split())
	print(r if r < l * 2 else -1)


for t in range(int(input())):
	(l, r) = map(int, input().split())
	if r - l + 1 <= l:
		print(r)
	else:
		print(-1)


for _ in range(int(input())):
	(L, R) = map(int, input().split())
	if R >= 2 * L or L == 1:
		print(-1)
	else:
		print(R)


t = input()
for c in range(0, int(t)):
	(l, r) = map(int, input().split())
	if r >= 2 * l or l == 1:
		print(-1)
	else:
		print(r)


def smallest_n(l: int, r: int) -> int:
	largest_remainder = r - l
	if largest_remainder >= l:
		return -1
	return r
T = int(input())
for _ in range(T):
	(L, R) = list(map(int, input().split()))
	print(smallest_n(L, R))


get_int = lambda : int(input())
get_mint = lambda : list(map(int, input().split()))
for _ in range(get_int()):
	(L, R) = get_mint()
	if 2 * L <= R:
		print(-1)
		continue
	print(R)


for _ in range(int(input())):
	(L, R) = list(map(int, input().split()))
	if (L, R) == (1, 2):
		print(-1)
		continue
	if L > R // 2:
		print(R)
	else:
		print(-1)


from sys import stdin, stdout
stdint = lambda : int(stdin.readline())
mul = lambda : map(int, stdin.readline().strip().split())
for _ in range(stdint()):
	(l, r) = mul()
	if l > r // 2:
		print(r)
	else:
		print(-1)


for a in range(int(input())):
	(L, R) = map(int, input().split())
	if R / L >= 2:
		print('-1')
	else:
		print(R)


t = int(input())
for _ in range(t):
	(L, R) = map(int, input().split())
	if L == 1:
		print(-1)
	elif L > R // 2:
		print(R)
	else:
		print(-1)


def number_cond(st, end):
	if end - st < st:
		return end
	else:
		return -1
t = int(input())
for _ in range(t):
	(st, end) = list(map(int, input().split()))
	if st == 1:
		print(-1)
	else:
		print(number_cond(st, end))


t = int(input())
for i in range(t):
	(l, r) = map(int, input().split())
	if r >= 2 * l or l == 1:
		print('-1')
	else:
		print(r)


t = int(input())
for i in range(t):
	l = list(map(int, input().split()))
	x = l[0]
	y = l[1]
	if y < 2 * x:
		print(y)
	else:
		print(-1)


t = int(input())
while t > 0:
	t -= 1
	(l, r) = list(map(int, input().split()))
	if l > r // 2:
		print(r)
	else:
		print(-1)


T = int(input())
for x in range(T):
	(l, r) = map(int, input().split())
	if l == 1:
		print(-1)
	elif l > r // 2:
		print(r)
	else:
		print(-1)


def ans(a, b):
	if b >= 2 * a:
		return -1
	return b
for _ in range(int(input())):
	(a, b) = map(int, input().split())
	print(ans(a, b))


for _ in range(int(input())):
	(L, R) = [int(s) for s in input().split()]
	if R // L == 1:
		print(R)
	else:
		print(-1)


for _ in range(int(input())):
	nums = list(map(int, input().split()))
	if nums[-1] < 2 * nums[0]:
		print(nums[-1])
	else:
		print('-1')


def findNum(l, r):
	if 2 * l > r:
		return r
	return -1
for _ in range(int(input())):
	(l, r) = map(int, input().split())
	print(findNum(l, r))


t = int(input())
for _ in range(t):
	(L, R) = map(int, input().split())
	if R % L != 0 and L * 2 > R:
		print(R)
	else:
		print(-1)


tc = int(input())
for _ in range(1, 1 + tc):
	ans = -1
	(l, r) = list(map(int, input().split()))
	if r >= 2 * l:
		print(-1)
	else:
		print(r)


import math
t = int(input())
for _ in range(t):
	(l, r) = map(int, input().split())
	gcd = math.gcd(l, r)
	if r - l < l:
		print(r)
	else:
		print(-1)


for m in range(int(input())):
	(a, b) = map(int, input().split())
	if a == 1 or b == 1 or b % a == 0 or (b % a < b - a):
		print(-1)
	else:
		print(max(0, a, b))


n = int(input())
for i in range(n):
	(a, b) = map(int, input().split())
	l = []
	c = 0
	if b < 2 * a:
		print(b)
	else:
		print('-1')


case = int(input())
for i in range(case):
	(L, R) = map(int, input().split(' '))
	if R < 2 * L:
		ans = R
	else:
		ans = -1
	print(ans)