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

Chef is a network engineer at CodeChef. Currently, he has to design a network that connects $N$ computers (numbered $1$ through $N$).

The network should consist of these $N$ computers and exactly $M$ cables. Usually, a cable needs to connect two different computers, but Chef is okay with connecting computers to themselves too. Therefore, let's describe a cable by the pair of computers $(u, v)$ it connects, where $1 ≤ u ≤ v ≤ N$. However, for each valid pair of computers $(u, v)$, there must be at most one cable that directly connects this pair of computers.

Let's define the *data consumption factor* of a computer as the number of computers which are directly connected to it. In particular, if a computer $v$ is directly connected to itself (by a cable $(v, v)$), it is only counted as connected to itself once. The data consumption factor of the whole network is the maximum of data consumption factors of all computers.

In the resulting network, each computer needs to be connected (directly or indirectly) to all other computers, so that they could communicate with each other.

Determine whether it is possible to design such a network. If it is possible, find the minimum possible data consumption factor of the resulting network.

------  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 $N$ and $M$.

------  Output ------
For each test case, print a single line containing one integer ― the minimum data consumption factor or $-1$ if Chef cannot design a required network.

------  Constraints  ------
$1 ≤ T ≤ 5 \cdot 10^{5}$
$1 ≤ N ≤ 10^{6}$
$0 ≤ M ≤ 10^{15}$

------  Subtasks ------
Subtask #1 (10 points):
$1 ≤ N ≤ 10$
$0 ≤ M ≤ 10^{3}$

Subtask #2 (10 points): $1 ≤ T ≤ 10^{2}$

Subtask #3 (10 points): $1 ≤ T ≤ 10^{3}$

Subtask #4 (70 points): original constraints

----- Sample Input 1 ------ 
3

2 3

5 6

3 3
----- Sample Output 1 ------ 
2

2

2
----- explanation 1 ------ 
Example case 1: The optimal configuration (and the only configuration) of computers is to connect computers $1$ and $2$, connect computer $1$ to itself and computer $2$ to itself. Then, the consumption factor of each computer is $2$ because it is directly connected to itself and the other computer.

Example case 3: Here, the cables can connect pairs of computers $(1, 2)$, $(1, 3)$ and $(2, 3)$. The consumption factor of each computer is $2$. There is a configuration with consumption factor $1$, where each computer is connected to itself, but all the computers are not connected, so this network configuration is invalid.

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Constructive algorithms

Mathematics

Data structures

Ad-hoc
Skill types: Data structures

Starter code:

Solutions:
for i in range(int(input())):
	(n, m) = map(int, input().split())
	if m < n - 1 or m > n * (n + 1) // 2:
		print(-1)
	elif n == 1 and m == 1:
		print(1)
	elif n == 1 and m == 0:
		print(0)
	elif n == 2 and m == 1:
		print(1)
	elif n == 2:
		print(2)
	elif m <= n + 1:
		print(2)
	elif m <= 2 * n:
		print(3)
	else:
		m = m - 2 * n
		ans = 3
		t1 = 2 * m // n
		t2 = 2 * m % n
		if t2:
			ans += t1 + 1
		else:
			ans += t1
		print(ans)


t = int(input())
for i in range(t):
	(n, m) = list(map(int, input().split()))
	if m < n - 1:
		print(-1)
	elif m > n * (n - 1) // 2 + n:
		print(-1)
	elif n == 1:
		if m == 0:
			print(0)
		else:
			print(1)
	elif n == 2:
		if m == 1:
			print(1)
		else:
			print(2)
	elif m >= n - 1 and m <= n + 1:
		print(2)
	elif m > n + 1 and m <= 2 * n:
		print(3)
	elif n % 2 == 0:
		n1 = n // 2
		ans = m // n1
		if m % n1 == 0:
			ans -= 1
		print(ans)
	else:
		ans = m // n
		if m % n == 0:
			ans -= 1
		ans *= 2
		if m % n > n // 2 or m % n == 0:
			ans += 1
		print(ans)


import math

def get_max_edges(n):
	return n * (n + 1) // 2
t = int(input())
for _ in range(t):
	l = list(map(int, input().strip().split()))
	(n, m) = (l[0], l[1])
	if m < n - 1 or m > get_max_edges(n):
		print(-1)
	elif m <= n + 1:
		if n == 1:
			if m == 0:
				print(0)
			elif m == 1:
				print(1)
			else:
				print(-1)
		elif n == 2:
			if m == 1:
				print(1)
			else:
				print(2)
		else:
			print(2)
	elif m <= 2 * n - 1:
		print(3)
	else:
		print(math.ceil(2 * (m - n) / n) + 1)


t = int(input())
for i in range(t):
	(n, m) = list(map(int, input().split()))
	if m < n - 1 or m > n * (n + 1) // 2:
		print(-1)
	elif m == n * (n + 1) // 2:
		print(n)
	elif m < n + 2:
		if n == 2 and m == 1:
			print(1)
		elif m == 0:
			print(0)
		else:
			print(2)
	elif m >= n + 2 and m <= 2 * n:
		print(3)
	else:
		var = m - n
		var1 = var * 2 // n
		if var * 2 % n == 0:
			print(1 + var1)
		else:
			print(2 + var1)


import math

def Network(n, m):
	upperLimit = n * (n + 1) // 2
	lowerLimit = n - 1
	if (n == 2 or n == 1) and m == 1:
		return 1
	if n == 1 and m == 0:
		return 0
	if m > upperLimit or m < lowerLimit:
		return -1
	elif m <= n + 1:
		return 2
	elif m <= 2 * n:
		return 3
	else:
		x = math.ceil(m / n)
		if m % n <= n // 2 and m % n != 0:
			return 2 * x - 2
		else:
			return 2 * x - 1
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().strip().split(' '))
	print(Network(n, m))


t = int(input())
while t:
	(n, m) = map(int, input().split())
	if n == 1:
		if m == 0:
			print(0)
		elif m == 1:
			print(1)
		else:
			print(-1)
	elif n == 2:
		if m == 0:
			print(-1)
		elif m == 1:
			print(1)
		elif m == 2 or m == 3:
			print(2)
		else:
			print(-1)
	elif m > n + n * (n - 1) / 2 or m < n - 1:
		print(-1)
	elif m >= n - 1 and m <= n + 1:
		print(2)
	elif m >= n + 2 and m <= 2 * n:
		print(3)
	elif n == 3:
		print(-1)
	elif n % 2 == 0:
		m -= 2 * n
		x = n // 2
		q = m // x
		r = m % x
		if r == 0:
			print(3 + q)
		else:
			print(4 + q)
	else:
		m -= 2 * n
		x = n // 2
		q = m // n
		r = m % n
		if r == 0:
			print(3 + q * 2)
		elif r <= x:
			print(3 + 2 * (q + 1) - 1)
		else:
			print(3 + 2 * (q + 1))
	t = t - 1


import math
t = int(input())
while t:
	(n, k) = map(int, input().split())
	ans = 0
	if k < n - 1 or k > n * (n + 1) // 2:
		ans = -1
	elif k >= n - 1 and k <= n + 1:
		if n == 1 or n == 2:
			if n == 1:
				if k <= n:
					ans = k
			elif k == 1:
				ans = k
			else:
				ans = 2
		else:
			ans = 2
	elif k > n + 1 and k <= n * 2:
		ans = 3
	else:
		x = math.ceil(k / n)
		if k % n <= n // 2 and k % n != 0:
			ans = 2 * x - 2
		else:
			ans = 2 * x - 1
	print(ans)
	t -= 1


rr = lambda : input().strip()
rri = lambda : int(rr())
rrm = lambda : [int(x) for x in rr().split()]

def sol(n, m):
	if m < n - 1 or m > (n + 1) * n // 2:
		return -1
	elif n == 1 and m == 0:
		return 0
	elif m == 1 and n == 2 or (n == 1 and m == 1):
		return 1
	elif m <= n + 1:
		return 2
	elif m <= 2 * n:
		return 3
	else:
		res = 3 + 2 * ((m - 2 * n) // n)
		if m % n == 0:
			return res
		elif m % n <= n // 2:
			return res + 1
		else:
			return res + 2
T = rri()
for _ in range(T):
	(n, m) = rrm()
	ans = sol(n, m)
	print(ans)


t = int(input())
while t > 0:
	(n, m) = map(int, input().split())
	if n == 1 and m == 1:
		print(1)
	elif n == 2 and m == 1:
		print(1)
	elif n == 1 and m == 0:
		print(0)
	elif m < n - 1:
		print('-1')
	elif m > n * (n + 1) // 2:
		print('-1')
	elif m <= n + 1:
		print('2')
	elif m <= 2 * n:
		print(3)
	else:
		m = m - 2 * n
		if n % 2 == 0:
			a = n // 2
			b = m // a
			if m % a == 0:
				print(3 + b)
			else:
				print(4 + b)
		else:
			b = m // n
			if m % n == 0:
				print(3 + 2 * b)
			else:
				u = m % n
				if u <= n // 2:
					print(4 + 2 * b)
				else:
					print(5 + 2 * b)
	t = t - 1


for i in range(int(input())):
	(n, k) = map(int, input().split())
	if k < n - 1 or k > n * (n + 1) // 2:
		print(-1)
	elif n == 1 and k == 1:
		print(1)
	elif n == 1 and k == 0:
		print(0)
	elif n == 2 and k == 1:
		print(1)
	elif n == 2:
		print(2)
	elif k <= n + 1:
		print(2)
	elif k <= 2 * n:
		print(3)
	else:
		k = k - 2 * n
		p = 3
		temp1 = 2 * k // n
		temp2 = 2 * k % n
		if temp2:
			p += temp1 + 1
		else:
			p += temp1
		print(p)


from math import ceil
for _ in range(int(input())):
	(n, m) = list(map(int, input().split()))
	maximum = n * (n + 1) // 2
	minimum = n - 1
	if m < minimum or m > maximum:
		print(-1)
	elif n == 1:
		if m == 0:
			print(0)
		elif m == 1:
			print(1)
		else:
			print(-1)
	elif n == 2:
		if m == 1:
			print(1)
		else:
			print(2)
	elif m == n - 1 or m == n or m == n + 1:
		print(2)
	elif m > 2 * n:
		x = m - n
		x = x * 2
		if x % n == 0:
			y = ceil(x / n)
			y += 1
		else:
			y = x // n
			y += 2
		print(y)
	else:
		print(3)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	aj = n - 1
	bj = n * (n - 1) / 2 + n
	if m >= aj and m <= bj:
		if n == 1:
			so1 = [0, 1]
			print(so1[m])
		elif n == 2:
			so2 = [1, 2, 2]
			print(so2[m - 1])
		elif m < aj + 3:
			print(2)
		elif m <= n * 2:
			print(3)
		else:
			div = (m - 1) // n * 2
			pre = m - m % n
			if pre == m:
				pre = pre - n
			if m <= pre + n // 2:
				print(div)
			else:
				print(div + 1)
	else:
		print('-1')


def m():
	t = int(input())
	while t > 0:
		(n, m) = map(int, input().split())
		if m < n - 1 or m > n * (n + 1) / 2:
			print(-1)
		elif m == 0:
			print(0)
		elif n == 1 and m == 1 or (n == 2 and m == 1):
			print(1)
		elif n == 1 and m >= 2:
			print(-1)
		elif m == n - 1 or m == n or m == n + 1:
			print(2)
		elif m <= 2 * n and m > n + 1:
			print(3)
		else:
			m -= 2 * n
			rem = n % 2
			if rem == 0:
				quot = n // 2
				k1 = m % quot
				k2 = m // quot
				if k1 == 0:
					print(3 + k2)
				elif k1 != 0:
					print(3 + k2 + 1)
			elif rem != 0:
				quot = n // 2 + 1
				k1 = m // n
				k2 = m % n
				if k2 < quot and k2 == 0:
					print(k1 * 2 + 3)
				elif k2 < quot and k2 != 0:
					print(k1 * 2 + 3 + 1)
				elif k2 >= quot:
					print(k1 * 2 + 3 + 2)
		t -= 1
m()


import sys, math
f = None
try:
	f = open('input1.txt', 'r')
except IOError:
	f = sys.stdin

def print_case_iterable(case_num, iterable):
	print('Case #{}: {}'.format(case_num, ' '.join(map(str, iterable))))

def print_case_number(case_num, iterable):
	print('Case #{}: {}'.format(case_num, iterable))

def rl():
	return int(f.readline())

def rln():
	return [int(x) for x in f.readline().split(' ')]

def rns():
	a = [x for x in f.readline().split(' ')]
	return (int(a[0]), a[1].strip())

def rs():
	return list(f.readline())
from math import factorial as fac

def binomial(x, y):
	try:
		binom = fac(x) // fac(y) // fac(x - y)
	except ValueError:
		binom = 0
	return binom

def solution(N, M):
	if N == 1:
		if M > 1:
			return -1
		return M
	if N == 2:
		if M == 1:
			return 1
		if M in [2, 3]:
			return 2
		return -1
	if M > N + N * (N - 1) // 2 or M < N - 1:
		return -1
	if M <= N + 1:
		return 2
	if M <= 2 * N:
		return 3
	M = M - N
	return 1 + math.ceil(2 * M / N)
T = int(input())
for i in range(T):
	(N, M) = [int(x) for x in input().split(' ')]
	print(solution(N, M))


import math
t = int(input())
while t:
	t -= 1
	(n, m) = input().split()
	n = int(n)
	m = int(m)
	if n <= 2:
		if n == 1:
			if m == 0:
				ans = 0
			elif m == 1:
				ans = 1
			else:
				ans = -1
		elif n == 2:
			if m == 1:
				ans = 1
			elif m == 2:
				ans = 2
			elif m == 3:
				ans = 2
			else:
				ans = -1
	elif m < n - 1 or m > n * (n + 1) / 2:
		ans = -1
	elif m <= n + 1:
		ans = 2
	elif m <= 2 * n and m > n + 1:
		ans = 3
	elif m > 2 * n:
		e = m - n
		deg = 2 * e
		ans = math.ceil(deg / n) + 1
	print(ans)


t = int(input())
while t:
	(n, m) = map(int, input().split())
	sum1 = n * (n + 1) // 2
	if n == 1 and m == 0:
		print(0)
	elif n == 1 and m == 1:
		print(1)
	elif n == 2 and m == 1:
		print(1)
	elif m < n - 1 or m == 0 or m > sum1:
		print(-1)
	elif m >= n - 1 and m <= n + 1 and (n != 1):
		print(2)
	elif m <= 2 * n:
		print(3)
	elif n % 2 == 0:
		x = n // 2
		y = m - 2 * n
		k = y // x
		if y % x != 0:
			k += 1
		print(k + 3)
	elif n % 2 != 0:
		x = n
		y = 2 * (m - 2 * n)
		k = y // x
		if y % x != 0:
			k += 1
		print(k + 3)
	t -= 1


__author__ = 'Ronald Kaiser'
__email__ = 'raios dot catodicos at gmail dot com'
for _ in range(int(input())):
	(N, M) = list(map(int, input().split()))
	if N == 1 and M == 0:
		print(0)
	elif N == 1 and N == M or (N == 2 and M == 1):
		print(1)
	elif M < N - 1 or M > N * (N + 1) / 2:
		print(-1)
	elif N - 1 <= M <= N + 1:
		print(2)
	elif N + 2 <= M <= N << 1:
		print(3)
	else:
		x = 4 + int((M / N - 2) // 0.5)
		if (M / N - 2) % 0.5 == 0:
			x -= 1
		print(x)


import math
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if m < n - 1 or m > n * (n + 1) / 2:
		print(-1)
	elif n <= 2 and m == 1:
		print(1)
	elif m == 0:
		print(0)
	elif m <= 2 * n:
		if m <= n + 1:
			print(2)
		else:
			print(3)
	else:
		m -= 2 * n
		c = math.floor(n / 2)
		if n % 2 == 0:
			print(math.ceil(m / c) + 3)
		else:
			z = m % n
			d = math.ceil(m / n) - 1
			ans = 2 * d + 3
			if z <= c:
				if z == 0:
					ans += 2
				else:
					ans += 1
			else:
				ans += 2
			print(ans)


pp = [0, 1]
for i in range(2, 10 ** 6 + 2):
	pp.append(pp[-1] + i)
n = int(input())
while n:
	(m, k) = map(int, input().split())
	if m == 1:
		l = [0, 1]
		if k >= 2:
			print(-1)
		else:
			print(l[k])
	elif m == 2:
		l = [-1, 1, 2, 2]
		if k >= 4:
			print(-1)
		else:
			print(l[k])
	elif m == 3:
		l = [-1, -1, 2, 2, 2, 3, 3]
		if k >= 7:
			print(-1)
		else:
			print(l[k])
	elif m == 4:
		l = [-1, -1, -1, 2, 2, 2, 3, 3, 3, 4, 4]
		if k >= 11:
			print(-1)
		else:
			print(l[k])
	elif k < m - 1 or k >= pp[m] + 1:
		print(-1)
	elif k >= m - 1 and k < m + 2:
		print(2)
	elif k >= m + 2 and k < 2 * m + 1:
		print(3)
	else:
		y = k - (2 * m + 1)
		u = m // 2
		if k % m == 0:
			k = k // m - 1
		else:
			k = k // m
		if y % m < u:
			print(4 + (k - 2) * 2)
		else:
			print(5 + (k - 2) * 2)
	n -= 1


from math import ceil
for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	result = 0
	if n == 1:
		if m == 0:
			result = 0
		elif m == 1:
			result = 1
		else:
			result = -1
	elif n == 2:
		if m == 1:
			result = 1
		elif m > 1 and m <= 3:
			result = 2
		else:
			result = -1
	elif m < n - 1 or m > n * (n + 1) // 2:
		result = -1
	elif m >= n - 1 and m <= n + 1:
		result = 2
	elif m > n + 1 and m <= 2 * n:
		result = 3
	else:
		x = m - 2 * n
		y = n / 2
		result = ceil(x / y) + 3
	print(result)


import math
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	maxm = n * (n - 1) // 2 + n
	ans = -1
	if n == 1 and m == 0:
		print(0)
		continue
	if n == 1 and m == 1:
		print(1)
		continue
	if n == 2 and m == 1:
		print(1)
		continue
	if m > maxm:
		print(-1)
		continue
	if m < n - 1 or m == 0:
		print(-1)
		continue
	if m == n - 1:
		print(2)
		continue
	if m <= n + 1:
		print(2)
		continue
	if m <= n + 1 + n - 2:
		print(3)
		continue
	if m == 2 * n:
		print(3)
		continue
	if m > 2 * n:
		ans = 3
		m -= 2 * n
		if n % 2 == 0:
			ans += math.ceil(m / (n // 2))
		else:
			newans = math.ceil(m / n) * 2
			if m + n - n * math.ceil(m / n) > n / 2:
				ans += newans
			else:
				ans += newans - 1
		print(ans)


import math
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	maxm = n * (n - 1) // 2 + n
	ans = -1
	if n == 1 and m == 0:
		print(0)
		continue
	if n == 2 and m == 1:
		print(1)
		continue
	if n == 1 and m == 1:
		print(1)
		continue
	if m > maxm:
		print(-1)
		continue
	if m < n - 1 or m == 0:
		print(-1)
		continue
	if m < n + 2:
		print(2)
		continue
	if m >= n + 2 and m <= 2 * n:
		print(3)
		continue
	elif m > 2 * n:
		ans = 3
		orig_m = m
		m -= 2 * n
		if n % 2 == 0:
			ans += math.ceil(m / (n // 2))
		else:
			x = math.ceil(m / n)
			y = 2 * x + 2
			z = m + 2 * n - n * (x + 1)
			p = n / 2
			if z > p:
				ans = y + 1
			else:
				ans = y
	print(ans)


import math
testcases = int(input())
for t in range(testcases):
	(N, M) = map(int, input().split())
	if M < N - 1 or M > N * (N + 1) / 2:
		print(-1)
	elif N <= 2 and M == 1:
		print(1)
	elif M == 0:
		print(0)
	elif M <= 2 * N:
		if M <= N + 1:
			print(2)
		else:
			print(3)
	else:
		M -= 2 * N
		P = math.floor(N / 2)
		if N % 2 == 0:
			print(math.ceil(M / P) + 3)
		else:
			Q = math.ceil(N / 2)
			R = M % N
			D = math.ceil(M / N) - 1
			result = 2 * D + 3
			if R <= P:
				if R == 0:
					result += 2
				else:
					result += 1
			else:
				result += 2
			print(result)


import math

def net(n, m):
	val4 = int(n / 2)
	valu4 = math.ceil(n / 2)
	subTotal = 2 * n + val4
	loop = int(n * (n + 1) / 2)
	mcp = m - subTotal
	if m <= n - 2 or m > loop:
		print(-1)
	elif n <= 2 and m == 1:
		print(1)
	elif m == 0:
		print(0)
	elif n - 1 <= m <= n + 1:
		print(2)
	elif n + 2 <= m <= 2 * n:
		print(3)
	elif 2 * n + 1 <= m <= 2 * n + val4:
		print(4)
	else:
		startNum = 5
		updateNum = math.ceil(mcp / n)
		if 1 <= mcp % n <= valu4:
			print(startNum + (updateNum - 1) * 2)
		else:
			print(startNum + 1 + (updateNum - 1) * 2)
for _ in range(int(input())):
	arr = list(map(int, input().split()))
	(n, m) = (arr[0], arr[1])
	net(n, m)


from sys import stdin
from math import ceil

def solve():
	t = int(stdin.readline().strip())
	for _ in range(t):
		(n, m) = list(map(int, stdin.readline().strip().split()))
		if m < n - 1 or m > n + n * (n - 1) // 2:
			print(-1)
		else:
			regular_edges = max(n - 1, m - n)
			print(ceil((regular_edges + m) / n))
solve()


import math
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if m < n - 1 or m > n * (n + 1) / 2:
		print(-1)
	elif n == 1 and m == 0:
		print(0)
	elif m == 1:
		print(1)
	elif m <= n + 1:
		print(2)
	else:
		l = m - 2 * n
		if l > 0:
			print(math.ceil(l * 2 / n) + 3)
		else:
			print(3)


t = int(input())
mod = 100000007
for i in range(t):
	(n, m) = map(int, input().split())
	ans = 0
	if n == 1:
		if m == 0:
			print(0)
		elif m == 1:
			print(1)
		else:
			print(-1)
	elif n == 2:
		if m == 1:
			print(1)
		elif m == 2 or m == 3:
			print(2)
		else:
			print(-1)
	elif m < n - 1 or m > n * (n + 1) // 2:
		print(-1)
	elif m == n - 1 or m == n or m == n + 1:
		ans = 2
		print(ans)
	elif n + 2 <= m <= 2 * n:
		ans = 3
		print(ans)
	else:
		quo = (m - 2 * n - 1) // n
		rem = (m - 2 * n - 1) % n
		if 0 <= rem <= n // 2 - 1:
			print(2 * quo + 4)
		else:
			print(2 * quo + 5)


import math
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	lim = n * (n + 1) // 2
	if n == 1 and m == 0:
		print(0)
		continue
	if n == 2 and m == 1:
		print(1)
		continue
	if n == 1 and m == 1:
		print(1)
		continue
	if m > lim:
		print(-1)
		continue
	if m < n - 1 or m == 0:
		print(-1)
		continue
	if m < n + 2:
		print(2)
		continue
	if m >= n + 2 and m <= 2 * n:
		print(3)
		continue
	if n % 2:
		id = m - 2 * n
		x = math.ceil(id / n)
		y = 2 * x + 2
		z = m - n * (x + 1)
		p = n / 2
		if z > p:
			print(y + 1)
		else:
			print(y)
	else:
		id = m - 2 * n
		x = math.ceil(id / (n // 2))
		print(x + 3)


p = int(input())
while p > 0:
	(n, m) = map(int, input().split())
	if m < n - 1 or m > int(n * (n + 1) / 2):
		print(-1)
	elif m == 0 and n == 1:
		print(0)
	elif n == 1 and m == 1:
		print(1)
	elif n == 2:
		if m == 1:
			print(1)
		else:
			print(2)
	elif m == n - 1 or m == n or m == n + 1:
		print(2)
	elif m <= 2 * n:
		print(3)
	else:
		t = int((m - 2 * n) / n)
		ans = 4 + t * 2
		if (m - 2 * n) % n > int(n / 2):
			ans += 1
		if (m - 2 * n) % n == 0:
			ans -= 1
		print(ans)
	p -= 1


test = int(input())
import math
while test != 0:
	(n, m) = map(int, input().split())
	if n == 1:
		if m == 0:
			print(0)
		elif m == 1:
			print(1)
		else:
			print(-1)
	elif n == 2:
		if m == 1:
			print(1)
		elif m > 1 and m <= 3:
			print(2)
		else:
			print(-1)
	elif m < n - 1 or m > n * (n + 1) // 2:
		print(-1)
	elif m >= n - 1 and m <= n + 1:
		print(2)
	elif m > n + 1 and m <= 2 * n:
		print(3)
	else:
		x = m - 2 * n
		y = n / 2
		print(math.ceil(x / y) + 3)
	test -= 1


t = int(input())
for _ in range(t):
	x = 0
	y = 0
	p = 0
	s = 0
	re = 0
	r = 0
	mi = 0
	ma = 0
	mid = 0
	sum = 0
	f = 0
	l = [int(x) for x in input().split()]
	l = l[:2]
	n = l[0]
	m = l[1]
	if n == 1:
		if m == 0:
			print(0)
			f = 1
		elif m == 1:
			print(1)
			f = 1
		else:
			print(-1)
			f = 1
	elif n == 2:
		if m == 1:
			print(1)
			f = 1
		elif m == 2 or m == 3:
			print(2)
			f = 1
		else:
			print(-1)
			f = 1
	elif n == 3:
		if m >= 2 and m <= 4:
			print(2)
			f = 1
		elif m == 5 or m == 6:
			print(3)
			f = 1
		else:
			print(-1)
			f = 1
	elif n == 4:
		if m >= 3 and m <= 5:
			print(2)
			f = 1
		elif m >= 6 and m <= 8:
			print(3)
			f = 1
		elif m >= 9 and m <= 10:
			print(4)
			f = 1
		else:
			print(-1)
	elif n == 5:
		if m >= 4 and m <= 6:
			print(2)
			f = 1
		elif m >= 7 and m <= 10:
			print(3)
			f = 1
		elif m >= 11 and m <= 12:
			print(4)
			f = 1
		elif m >= 13 and m <= 15:
			print(5)
			f = 1
		else:
			print(-1)
			f = 1
	elif n == 6:
		if m >= 5 and m <= 7:
			print(2)
			f = 1
		elif m >= 8 and m <= 12:
			print(3)
			f = 1
		elif m >= 13 and m <= 15:
			print(4)
			f = 1
		elif m >= 16 and m <= 18:
			print(5)
			f = 1
		elif m >= 19 and m <= 21:
			print(6)
			f = 1
		else:
			print(-1)
			f = 1
	elif n == 7:
		if m >= 6 and m <= 8:
			print(2)
			f = 1
		elif m >= 9 and m <= 14:
			print(3)
			f = 1
		elif m >= 15 and m <= 17:
			print(4)
			f = 1
		elif m >= 18 and m <= 21:
			print(5)
			f = 1
		elif m >= 22 and m <= 24:
			print(6)
			f = 1
		elif m >= 25 and m <= 28:
			print(7)
			f = 1
		else:
			print(-1)
			f = 1
	elif n == 8:
		if m >= 7 and m <= 9:
			print(2)
			f = 1
		elif m >= 10 and m <= 16:
			print(3)
			f = 1
		elif m >= 17 and m <= 20:
			print(4)
			f = 1
		elif m >= 21 and m <= 24:
			print(5)
			f = 1
		elif m >= 25 and m <= 28:
			print(6)
			f = 1
		elif m >= 29 and m <= 32:
			print(7)
			f = 1
		elif m >= 33 and m <= 36:
			print(8)
			f = 1
		else:
			print(-1)
			f = 1
	elif n == 9:
		if m >= 8 and m <= 10:
			print(2)
			f = 1
		elif m >= 11 and m <= 18:
			print(3)
			f = 1
		elif m >= 19 and m <= 22:
			print(4)
			f = 1
		elif m >= 23 and m <= 27:
			print(5)
			f = 1
		elif m >= 28 and m <= 31:
			print(6)
			f = 1
		elif m >= 32 and m <= 36:
			print(7)
			f = 1
		elif m >= 37 and m <= 40:
			print(8)
			f = 1
		elif m >= 41 and m <= 45:
			print(9)
			f = 1
		else:
			print(-1)
			f = 1
	elif n == 10:
		if m >= 9 and m <= 11:
			print(2)
			f = 1
		elif m >= 12 and m <= 20:
			print(3)
			f = 1
		elif m >= 21 and m <= 25:
			print(4)
			f = 1
		elif m >= 26 and m <= 30:
			print(5)
			f = 1
		elif m >= 31 and m <= 35:
			print(6)
			f = 1
		elif m >= 36 and m <= 40:
			print(7)
			f = 1
		elif m >= 41 and m <= 45:
			print(8)
			f = 1
		elif m >= 46 and m <= 50:
			print(9)
			f = 1
		elif m >= 51 and m <= 55:
			print(10)
			f = 1
		else:
			print(-1)
			f = 1
	if f == 1:
		continue
	if n >= 11:
		x = n * (n - 1)
		ma = int(x / 2) + n
		mi = n - 1
		re = int(m / n)
		r = m % n
		mid = int(n / 2)
		y = n * 2
		sum = 2 * re
		s = sum - 1
		p = sum + 1
		if m < mi and m > ma:
			print(-1)
			continue
		if m >= mi and m <= n + 1:
			print(2)
			continue
		elif m >= n + 2 and m <= ma:
			if m <= y and m >= n + 2:
				print(3)
				continue
			elif r >= 1 and r <= mid:
				print(sum)
				continue
			elif re * n == m:
				print(s)
				continue
			else:
				print(p)
				continue
		else:
			print(-1)
			continue


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	if n > m and n - m == 1:
		if m == 0 and n > 1:
			print(-1)
		elif m == 1:
			print(1)
		elif n == 1 and m == 0:
			print(0)
		else:
			print(2)
	elif n == m:
		if n > 1:
			print(2)
		else:
			print(1)
	elif n < m and n > 1:
		if n % 2 == 0:
			c = m // n
			max_m = n * n // 2 + n // 2
			if m <= max_m:
				if m > n + 1 and m <= 2 * n:
					print(3)
				elif m > c * n and m <= c * n + n // 2:
					print(2 * c)
				elif m > c * n + n // 2 and m <= (c + 1) * n:
					print(2 * c + 1)
				elif m > n * n // 2 and m <= max_m:
					print(n)
				elif m % n == 0:
					print(m // n + (m // n - 1))
			else:
				print(-1)
		else:
			c = m // n
			max_m = n * (n // 2 + 1)
			if m <= max_m:
				if m > n + 1 and m <= 2 * n:
					print(3)
				elif m > c * n and m <= c * n + n // 2:
					print(2 * c)
				elif m > c * n + n // 2 and m <= (c + 1) * n:
					print(2 * c + 1)
				elif m > c * n + n // 2 and m <= (n // 2 + 1) * n:
					print(n)
				elif m % n == 0:
					print(m // n + (m // n - 1))
			else:
				print(-1)
	else:
		print(-1)


T = int(input())
for _ in range(T):
	(N, M) = (int(x) for x in input().split(' '))
	T_n = N * (N + 1) // 2
	if M < N - 1 or M > T_n:
		print(-1)
	elif N == 1:
		print(M)
	elif N == 2:
		if M == 1:
			print(1)
		else:
			print(2)
	elif M < N + 2:
		print(2)
	elif M < 2 * N + 1:
		print(3)
	else:
		tmp = M - (2 * N + 1)
		a = tmp // N
		b = tmp % N
		if b < N // 2:
			print(4 + 2 * a)
		else:
			print(4 + 2 * a + 1)


test = int(input())
for i in range(test):
	(n, m) = map(int, input().split())
	answer = 0
	if n == 1:
		if m == 0:
			print(0)
		elif m == 1:
			print(1)
		else:
			print(-1)
	elif n == 2:
		if m == 1:
			print(1)
		elif m == 2 or m == 3:
			print(2)
		else:
			print(-1)
	elif m < n - 1 or m > n * (n + 1) // 2:
		print(-1)
	elif m == n - 1 or m == n or m == n + 1:
		answer = 2
		print(answer)
	elif n + 2 <= m <= 2 * n:
		answer = 3
		print(answer)
	elif n % 2 == 0:
		quota = (m - 2 * n - 1) // n
		rem = (m - 2 * n - 1) % n
		if 0 <= rem <= n // 2 - 1:
			print(2 * quota + 4)
		else:
			print(2 * quota + 5)
	else:
		quota = (m - 2 * n - 1) // n
		rem = (m - 2 * n - 1) % n
		if 0 <= rem <= n // 2 - 1:
			print(2 * quota + 4)
		else:
			print(2 * quota + 5)


tc = int(input())
for ii in range(tc):
	(n, m) = map(int, input().split())
	a = n - 1
	b = n + 1
	c = 2 * n
	if n <= 2:
		if m == 0 or m >= n * 2:
			ans = -1
		elif m == 1:
			ans = 1
		else:
			ans = 2
		if m == 0 and n == 1:
			ans = 0
		print(ans)
		continue
	if m < a:
		m -= m
		ans = -1
	elif a <= m <= b:
		m -= m
		ans = 2
	elif b < m <= c:
		m -= m
		ans = 3
	else:
		ans = 3
		m -= c
	if m == 0:
		print(ans)
		continue
	x = n // 2 - 1
	y = 0
	f = m % n
	if n % 2 == 0:
		x -= 1
		y = 1
	if m // n <= x:
		ans += m // n * 2
		x -= m // n
		if 0 < f <= n // 2:
			if x > 0 or y > 0:
				ans += 1
			else:
				ans = -1
		elif n // 2 < f < n:
			if x > 0:
				ans += 2
			else:
				ans = -1
		else:
			ans = ans
	else:
		ans = -1
	print(ans)


import math
t = int(input())
for i in range(0, t):
	(n, m) = [int(x) for x in input().split()]
	if n == 1 and m <= n:
		print(m, end='\n')
	elif n == 2 and m == 1:
		print(m, end='\n')
	elif m < n - 1 or m > n * (n + 1) // 2:
		print('-1', end='\n')
	elif m <= n + 1:
		print('2', end='\n')
	elif m <= 2 * n:
		print('3', end='\n')
	elif n % 2 == 0:
		c = m // n
		while m > n:
			m = m % n
			if m == 0:
				print(2 * c - 1, end='\n')
			elif m <= n // 2:
				print(2 * c, end='\n')
			else:
				print(2 * c + 1, end='\n')
	else:
		a = m - 2 * n
		b = a // n
		c = a % n
		re = 3 + 2 * b
		if c == 0:
			print(re, end='\n')
		elif c <= n // 2:
			print(re + 1, end='\n')
		else:
			print(re + 2, end='\n')


from math import ceil

def calculate(n, m):
	if n == 1:
		if m <= 1:
			return m
		return -1
	if n == 2:
		if m == 1:
			return 1
		if m == 3 or m == 2:
			return 2
		return -1
	if m < n - 1 or m > n * (n + 1) // 2:
		return -1
	if n - 1 <= m <= n + 1:
		return 2
	if m <= 2 * n:
		return 3
	if n & 1:
		a = (m - 2 * n) % n
		b = 2 * ((m - 2 * n) // n) + 4
		if m % n == 0 and m // n >= 3:
			return b - 1
		if a <= n // 2:
			return b
		return b + 1
	return ceil((m - 2 * n) / (n // 2)) + 3
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	print(calculate(n, m))


import math
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if n == 1:
		if m == 1:
			print(1)
		elif m == 0:
			print(0)
		else:
			print(-1)
		continue
	mLast = int(n * (n + 1) // 2)
	mFirst = n - 1
	if mFirst > m or m > mLast:
		print(-1)
		continue
	if m == mLast:
		print(n)
		continue
	if n == 2:
		if m == 1:
			print(1)
		else:
			print(2)
		continue
	if m == mFirst or n == m or n + 1 == m:
		print(2)
		continue
	ans = 3
	temp = m - 2 * n
	if temp <= 0:
		print(ans)
		continue
	flr = n // 2
	tem = temp // n
	ans += 2 * tem
	temp -= tem * n
	if temp != 0 and temp <= flr:
		ans += 1
	elif temp > flr:
		ans += 2
	print(ans)


import math
loop = int(input())
for x in range(loop):
	(n, m) = map(int, input().split())
	if m < n - 1:
		print(-1)
	elif n == 1:
		if m == 1:
			print('1')
		elif m == 0:
			print('0')
		else:
			print('-1')
	elif n == 2:
		if m == 1:
			print('1')
		elif m <= 3:
			print('2')
		else:
			print('-1')
	elif m <= n + 1:
		print('2')
	elif m <= 2 * n:
		print('3')
	else:
		m = m - 2 * n
		if n % 2 == 0:
			ans = math.ceil(m / (n // 2))
		else:
			ans = 2 * math.floor(m / n)
			if m % n <= n // 2:
				if m % n != 0:
					ans = ans + 1
			else:
				ans = ans + 2
		if ans + 3 > n:
			ans = -4
		print(ans + 3)


from bisect import *

def finder(fac, m):
	if m % fac != 1:
		if m % fac == 0:
			return m - 1
		return m - m % fac + 1
	return m

def finder2(fac, m):
	if m % fac != 1:
		if m % fac == 0:
			return m + 1
		return m - m % fac + 1
	return m

def locate(a, d, tn):
	return (tn - a) // d + 1

def fun(n, m):
	if n % 2 == 0:
		m = finder(n // 2, m)
		p = locate(n * 2 + 1, n // 2, m)
		return p + 3
	else:
		m1 = m
		m = finder2(n, m)
		dpd = (n + 1) // 2
		p = locate(n * 2 + 1, n, m)
		if m1 - m + 1 == 0:
			return (p - 1) * 2 + 3
		elif m1 - m + 1 < dpd:
			return p * 2 + 2
		else:
			return p * 2 + 3

def fun2(n, m):
	d = {'1#0': 0, '1#1': 1, '2#1': 1, '2#2': 2, '2#3': 2, '3#2': 2, '3#3': 2, '3#4': 2, '3#5': 3, '3#6': 3}
	return d[str(n) + '#' + str(m)]
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if m < n - 1 or m > n * (n + 1) // 2:
		print(-1)
	elif n <= 3:
		print(fun2(n, m))
	elif m in (n - 1, n, n + 1):
		print(2)
	elif m < n * 2 + 1:
		print(3)
	else:
		print(fun(n, m))


import math
from numpy import *
t = int(input())
for i in range(0, t):
	(p, q) = [int(x) for x in input().split()]
	if p == 1 and q == 0:
		print('0')
	elif p == 1 and q == 1:
		print('1')
	elif p == 2 and q == 1:
		print('1')
	elif q == 0 or q < p - 1 or q > p * (p + 1) / 2:
		print('-1')
	elif q >= p - 1 and q <= p + 1:
		print('2')
	elif q > p + 1 and q <= 2 * p:
		print('3')
	else:
		a = q * 2 - p
		b = math.ceil(double(a / p))
		print(int(b))


import math
t = int(input())
for test in range(0, t):
	ans = 0
	(N, M) = input().split()
	N = int(N)
	M = int(M)
	if N == 1:
		if M == 0:
			print(0)
		elif M == 1:
			print(1)
		else:
			print(-1)
		continue
	if N == 2:
		if M == 0:
			print(-1)
		elif M == 1:
			print(1)
		elif M < 4:
			print(2)
		else:
			print(-1)
		continue
	if M < N - 1:
		print(-1)
		continue
	if M > N * (N + 1) // 2:
		print(-1)
		continue
	if M <= N + 1:
		print(2)
	elif M <= 2 * N:
		print(3)
	else:
		M -= 2 * N
		y = math.floor(N / 2)
		z = math.ceil(N / 2)
		x = 3
		r = M % (y + z)
		q = M // (y + z)
		x += q * 2
		if r != 0:
			if r <= y:
				x += 1
			else:
				x += 2
		print(x)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if n == 1:
		if m == 0:
			print(0)
		elif m == 1:
			print(1)
		else:
			print(-1)
	elif n == 2:
		if m == 1:
			print(1)
		elif m == 2 or m == 3:
			print(2)
		else:
			print(-1)
	elif m < n - 1 or m > n * (n - 1) // 2 + n:
		print(-1)
	elif m <= n + 1:
		print(2)
	elif m <= 2 * n:
		print(3)
	else:
		m = m - 2 * n
		req = 2 * m
		x = req // n
		y = req % n
		if y == 0:
			print(3 + x)
		else:
			print(3 + x + 1)


import math
from numpy import *
for _ in range(int(input())):
	(n, m) = (int(i) for i in input().split())
	b = 0
	if n == 1 and m == 0:
		print(0)
	elif m == 0 or m > n * (n + 1) / 2 or m < n - 1:
		print(-1)
	elif n == 2 and m == 1 or (n == 1 and m == 1):
		print(1)
	elif m >= n - 1 and m <= n + 1:
		print(2)
	elif m > n + 1 and m <= 2 * n:
		print(3)
	else:
		a = 2 * m - n
		b = int(math.ceil(double(a / n)))
		print(b)


from math import ceil
t = int(input())
for i in range(t):
	ans = -1
	(n, m) = map(int, input().split())
	if n == 1 and m == 0:
		print('0')
	elif m > n * (n - 1) // 2 + n:
		print('-1')
	elif m < n - 1:
		print('-1')
	elif n == 1 and m == 1:
		print('1')
	elif n == 2 and m == 1:
		print('1')
	elif m <= n + 1:
		print('2')
	elif m <= 2 * n:
		print('3')
	else:
		if n % 2 == 0:
			ans = 3
			rem = m - 2 * n
			q = rem // (n // 2)
			ans = ans + q
			r = rem % (n // 2)
			if r > 0:
				ans = ans + 1
		else:
			ans = 3
			rem = m - 2 * n
			q = rem // n
			r = rem % n
			rem = rem - n * q
			ans = ans + 2 * q
			if r > 0:
				if rem > 0 and rem <= n // 2:
					ans = ans + 1
				else:
					ans = ans + 2
		print(ans)


t = int(input())
for c in range(0, t):
	s1 = [int(i) for i in input().split()]
	(n, m) = (s1[0], s1[1])
	d = n / 2.0
	if n == 1 and m == 0:
		print(0)
	elif n == 1 and m == 1:
		print(1)
	elif n == 2 and m == 1:
		print(1)
	elif m < n - 1 or m > n * (n + 1) / 2:
		print(-1)
	elif m >= n - 1 and m <= n + 1:
		print(2)
	elif m >= n + 2 and m <= 2 * n:
		print(3)
	elif m > 2 * n:
		if n % 2 == 0:
			if int(m / d) == m / int(d):
				print(int(m / d) - 1)
			else:
				print(int(m / d))
		else:
			u = n / 2
			v = n / 2 + 1
			w = m % n
			if w == 0:
				print(int(m / d) - 1)
			else:
				print(int(m / d))


t = int(input())
while t:
	t = t - 1
	(n, m) = map(int, input().split())
	if m < n - 1 or m > (n + 1) * n // 2 or (m == 0 and n > 1):
		print(-1)
	elif n == 1:
		if m == 1:
			print(1)
		elif m == 0:
			print(0)
	elif n == 2 and m == 1:
		print(1)
	elif m <= n + 1:
		print(2)
	elif m <= 2 * n:
		print(3)
	else:
		c = 2 * n
		if n % 2 == 0:
			c = m - c
			k = 0
			if c % (n // 2) != 0:
				k = 1
			c = 3 + k + c // (n // 2)
			print(c)
		else:
			x = m // n
			x = x * 2
			if m % n == 0:
				print(x - 1)
			elif m % n <= n / 2:
				print(x)
			else:
				print(x + 1)


import math as mp

def nCr(n, r):
	if r == 0:
		return 1
	if r > n // 2:
		return nCr(n, n - r)
	re = 1
	for k in range(1, r + 1):
		re *= n - k + 1
		re = re // k
	return re
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	c = 0
	if n == 1:
		if m == 0:
			print('0')
		elif m == 1:
			print('1')
		else:
			print('-1')
	elif n == 2:
		if m == 2 or m == 3:
			print('2')
		elif m == 1:
			print('1')
		else:
			print('-1')
	elif m < n - 1 or m > n * (n + 1) // 2:
		print('-1')
	else:
		if m >= n - 1 and m <= n + 1:
			c = 2
		elif m > n + 1 and m <= 2 * n:
			c = 3
		else:
			c = 3
			m = m - 2 * n
			if n % 2 == 0:
				st = int(n / 2)
				f = mp.ceil(m / st)
				c = c + f
			else:
				s1 = int(n / 2)
				s2 = s1 + 1
				st = s1 + s2
				f = int(m / st)
				c += 2 * f
				rek = m % st
				if rek:
					if rek > s1:
						c += 2
					else:
						c += 1
		print(c)


import collections
import itertools
import math

def ans(n, m):
	if m < n - 1 or m > n * (n + 1) // 2:
		print('-1')
		return -11
	if n == 2:
		if m == 1:
			print('1')
			return -11
		if m == 2:
			print('2')
			return -11
		if m == 3:
			print('2')
			return -11
	if n == 1:
		if m == 0:
			print('0')
			return -11
		if m == 1:
			print('1')
			return -11
	temp = 2 * m - 4 * n
	k = math.ceil(temp / n)
	return k
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	k = ans(n, m)
	if k != -11:
		if m <= n + 1:
			print('2')
		elif m > n + 1 and m <= 2 * n:
			print('3')
		elif m > 2 * n and m <= 2 * n + n / 2:
			print('4')
		else:
			print(k + 3)


t = int(input())
for i1 in range(0, t):
	(n, m) = map(int, input().split())
	c = n * (n + 1) // 2
	if m < n - 1:
		ans = -1
	elif m > c:
		ans = -1
	elif m == n - 1:
		ans = min(2, n - 1)
	elif m == n:
		ans = min(2, n)
	elif m > n and m <= n + 1:
		ans = 2
	elif m > n and m <= 2 * n:
		ans = 3
	else:
		a1 = 2 * m // n
		if 2 * m % n == 0:
			ans = a1 - 1
		else:
			ans = a1
	print(ans)


t = int(input())
while t > 0:
	(n, m) = map(int, input().split())
	if m < n - 1 or m > n * (n + 1) // 2:
		print(-1)
	elif n == 1:
		print(m)
	elif n == 2:
		if m == 1:
			print(1)
		elif m <= 3:
			print(2)
	elif m <= n + 1 and m >= n - 1:
		print(2)
	elif m <= 2 * n and m > n + 1:
		print(3)
	elif n % 2 == 0:
		print(2 * (m - 1) // n)
	else:
		if n % 4 < 3:
			k = 2 * (n // 4)
		else:
			k = 2 * (n // 4) + 1
		d = 2 * ((m - 1) // n)
		if m % n <= k and m % n != 0:
			print(d)
		else:
			print(d + 1)
	t -= 1


import math
t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	if m < n - 1 or m > n * (n + 1) / 2:
		print(-1)
	elif n == 1:
		if m == 1:
			print(1)
		elif m == 0:
			print(0)
	elif n == 2:
		if m == 1:
			print(1)
		else:
			print(2)
	elif m < n + 2:
		print(2)
	elif m <= 2 * n:
		print(3)
	elif n % 4 == 0:
		m -= 2 * n
		k = 3
		total = n // 2
		if m % total == 0:
			k += m // total
		else:
			k += 1 + m // total
		print(k)
	elif n % 2 == 0:
		m -= 2 * n
		if m <= n / 2:
			print(4)
		else:
			k = 3
			total = m // n
			k += 2 * total
			m -= n * total
			int1 = -1 + n // 2
			int2 = 1 + n // 2
			if m <= n // 2 and m > 0:
				k += 1
			elif m > n // 2 and m < n:
				k += 2
			print(k)
	else:
		m -= 2 * n
		k = 3
		int1 = (n - 1) // 2
		int2 = (n + 1) // 2
		total = m // n
		k += 2 * total
		m -= n * total
		if m <= int1 and m > 0:
			k += 1
		elif m > int1 and m <= int1 + int2:
			k += 2
		print(k)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	upper_bound = n * (n + 1) // 2
	if m < n - 1 or m > upper_bound:
		print('-1')
	elif n == 1:
		print(m - n + 1)
	elif n == 2:
		if m - n + 1 == 0:
			print('1')
		elif m - n + 1 >= 1:
			print('2')
	elif m - n + 1 <= 2:
		print('2')
	elif 2 <= m - n + 1 <= n + 1:
		print('3')
	else:
		factor = n // 2
		if n % 2 == 1:
			p = (m - 2 * n - 1) // (2 * factor + 1)
			temp = 3 + (n - 1) + p * (2 * factor + 1)
		else:
			p = (m - 2 * n - 1) // (2 * factor)
			temp = 3 + (n - 1) + p * (2 * factor)
		if m - n + 2 <= factor + temp:
			print(2 * p + 4)
		else:
			print(2 * p + 5)


t = int(input())
for _ in range(t):
	l = list(map(int, input().split()))
	n = l[0]
	m = l[1]
	a = n * (n + 1) // 2
	b = {1: [0, 1], 2: [1, 2, 2], 3: [2, 2, 2, 3, 3]}
	if m < n - 1 or m > a:
		print('-1')
	elif n == 1 or n == 2 or n == 3:
		ans = b[n][m - n + 1]
		print(ans)
	elif n % 2 == 0:
		if m >= n - 1 and m <= n + 1:
			print(2)
		elif m > n + 1 and m <= 2 * n:
			print(3)
		else:
			c = m // (n // 2)
			d = m % (n // 2)
			if d != 0:
				print(int(c))
			elif d == 0:
				print(int(c - 1))
	elif m >= n - 1 and m <= n + 1:
		print(2)
	elif m > n + 1 and m <= 2 * n:
		print(3)
	else:
		c = m // n
		d = m % n
		if d > 0 and d <= n // 2:
			print(2 * c)
		elif d > n // 2 and d <= n - 1:
			print(2 * c + 1)
		elif d == 0:
			print(2 * c - 1)


T = int(input())
for _ in range(T):
	(n, m) = [int(i) for i in input().split()]
	if m < n - 1 or m > (n * n + n) // 2:
		print(-1)
	elif m == 0:
		print(0)
	elif n == 1:
		if m == 1:
			print(1)
		else:
			print(-1)
	elif n == 2 and m == 1:
		print(1)
	elif n - 1 <= m <= n + 1:
		print(2)
	elif m <= n * 2:
		print(3)
	else:
		kk = 2 * m // n
		if 2 * m % n == 0:
			kk = kk - 1
		print(kk)


import math
t = int(input())
for testcase in range(t):
	(n, m) = [int(i) for i in input().split()]
	maxm = n * (n - 1) / 2 + n
	if m < n - 1 or m > maxm:
		print(-1)
	elif n == 1:
		print(m)
	elif n == 2 and m == 1:
		print(1)
	elif m <= n + 1:
		print(2)
	elif m <= 2 * n:
		print(3)
	else:
		m -= 2 * n
		print(3 + int(math.ceil(m / (n / 2))))


for _ in range(int(input())):
	(n, m) = map(int, input().split(' '))
	ans = -1
	if m == 0 and n == 1:
		ans = 0
	elif m == 1 and n == 1:
		ans = 1
	elif m >= n - 1 and m <= n * (n - 1) // 2 + n:
		if n == 2:
			if m == 1:
				ans = 1
			elif m == 2 or m == 3:
				ans = 2
		else:
			arr = [n + 1, 2 * n]
			if arr[0] >= m:
				ans = 2
			elif arr[1] >= m:
				ans = 3
			else:
				a2 = 0
				N = m
				N -= n * 2 // 2 + n
				if n & 1 == 1:
					t1 = n // 2
					t2 = n // 2 + 1
					a2 = 4
					var = N % (t1 + t2)
					a2 += N // (t1 + t2) * 2
					if var > t1:
						a2 += 1
					if var == 0:
						a2 -= 1
					ans = a2
				else:
					t = n // 2
					a2 = 4
					a2 += N // t
					if N % t == 0:
						a2 -= 1
					ans = a2
	print(ans)


for i in range(0, int(input())):
	(n, m) = map(int, input().split())
	rem = m - 2 * n
	if m < n - 1 or m > n * (n + 1) // 2:
		print(-1)
	elif n == 1:
		if m == 0:
			print(0)
		elif m == 1:
			print(1)
		else:
			print(-1)
	elif n == 2:
		if m == 1:
			print(1)
		elif m == 2 or m == 3:
			print(2)
		else:
			print(-1)
	elif m >= n - 1 and m <= n + 1:
		print(2)
	elif m > n + 1 and m <= 2 * n:
		print(3)
	else:
		a = 3
		if n % 2 == 0:
			t = rem // (n / 2)
			a = a + t
			if rem % (n / 2) != 0:
				a = a + 1
			print(int(a))
		elif n % 2 != 0:
			t = rem // n * 2
			a = a + t
			if rem % n == 0:
				a = a + 0
			elif rem % n <= n // 2:
				a = a + 1
			elif rem % n > n // 2:
				a = a + 2
			print(int(a))


import math
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	if n == 1:
		if m == 0 or m == 1:
			print(m)
		else:
			print(-1)
	elif n == 2:
		if m == 1:
			print(1)
		elif m == 2 or m == 3:
			print(2)
		else:
			print(-1)
	elif m < n - 1 or m > n * (n + 1) // 2:
		print(-1)
	elif m == n or m == n + 1 or m == n - 1:
		print(2)
	elif n + 2 <= m <= 2 * n:
		print(3)
	elif m == n * (n + 1) // 2:
		print(n)
	else:
		m -= 2 * n
		x = n // 2
		mmodn = m % n
		ans = m // n
		if mmodn == 0:
			ans -= 1
		ans *= 2
		if not (mmodn > n // 2 or mmodn == 0):
			ans += 1
		else:
			ans += 2
		print(ans + 3)


import math
T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split(' '))
	if N == 1:
		if M == 0 or M == 1:
			print(M)
		else:
			print(-1)
	elif N == 2:
		if M == 3 or M == 2:
			print(2)
		elif M == 1:
			print(1)
		else:
			print(-1)
	elif N == 3:
		if M in [2, 3, 4]:
			print(2)
		elif M in [5, 6]:
			print(3)
		else:
			print(-1)
	elif M < N - 1 or M > N * (N + 1) / 2:
		print(-1)
	elif M == N - 1 or M == N + 1 or M == N:
		print(2)
	elif M >= N + 2 and M <= 2 * N:
		print(3)
	else:
		base = int(N / 2)
		terms = N - 3
		M = M - 2 * N
		if N % 2 == 0:
			div = base
			pov = math.ceil(M / div)
			print(3 + pov)
		else:
			x = M // N
			if M % N == 0:
				x -= 1
			a = 2 * x
			y = M % N
			if y == 0 or y > N // 2:
				a += 2
			else:
				a += 1
			print(a + 3)


t = int(input())
for i in range(t):
	(n, m) = [int(i) for i in input().split()]
	if n == 1 and m == 0:
		print(0)
		continue
	elif n == 1 and m == 1:
		print(1)
		continue
	elif m < n - 1 or m > n * (n + 1) / 2:
		print(-1)
		continue
	elif n == 2 and m == n - 1:
		print(1)
		continue
	elif m >= n - 1 and m <= n + 1:
		print(2)
		continue
	elif m >= n + 2 and m <= 2 * n:
		print(3)
		continue
	else:
		d = m // n
		if m / n == d:
			print(d * 2 - 1)
			continue
		elif m <= d * n + n // 2:
			print(d * 2)
			continue
		else:
			print(d * 2 + 1)
			continue


for tst in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	p = n % 2
	if n == 1:
		if m == 0:
			print(0)
		elif m == 1:
			print(1)
		else:
			print(-1)
	elif m > n * (n + 1) / 2 or m < n - 1:
		print(-1)
	elif n == 2:
		if m < 2:
			print(1)
		elif m < 4:
			print(2)
		else:
			print(-1)
	elif m <= n + 1:
		print(2)
	elif m <= 2 * n:
		print(3)
	else:
		s = 3
		if p == 1:
			s += (m - 2 * n) // n * 2
			dd = (m - 2 * n) % n
			if dd <= n // 2 and dd != 0:
				s += 1
			elif dd > n // 2:
				s += 2
		else:
			s += (m - 2 * n) // (n / 2)
			if (m - 2 * n) % (n / 2) > 0:
				s += 1
		print(int(s))


def method(n, m):
	if n == 1 and m == 0:
		return 0
	elif n == 1 and m == 1:
		return 1
	elif m < n - 1 or m > n * (n + 1) / 2:
		return -1
	elif n == 2 and m == n - 1:
		return 1
	elif m >= n - 1 and m <= n + 1:
		return 2
	elif m >= n + 2 and m <= 2 * n:
		return 3
	else:
		v = m / n
		d = m // n
		r = n // 2
		if v == d:
			return d * 2 - 1
		elif m <= d * n + r:
			return d * 2
		else:
			return d * 2 + 1
t = int(input())
for i in range(t):
	(n, m) = [int(i) for i in input().split()]
	print(method(n, m))


from math import ceil

def alternate_ap(a, d1, d2, n):
	n = n - 1
	(term1, term2) = (ceil(n / 2), n // 2)
	return a + term1 * d1 + term2 * d2
for t in range(int(input())):
	(n, m) = map(int, input().split())
	for m in range(m, m + 1):
		if m == 0 and n == 1:
			print(0)
		elif m < n - 1 or m > n * (n + 1) // 2:
			print(-1)
		elif m == 1:
			print(1)
		elif n == 2:
			print(2)
		elif n - 1 <= m and m <= n + 1:
			print(2)
		elif n + 2 <= m and m <= 2 * n:
			print(3)
		elif n & 1:
			d1 = n // 2
			d2 = n // 2 + 1
			a = 2 * n
			term = ceil(2 * (m - a) / (d1 + d2))
			print(term + 3)
		else:
			temp_m = m - 2 * n - 1
			temp_m = temp_m // (n // 2)
			if temp_m < n - 3:
				print(temp_m + 4)
			else:
				print(n)


for ij in range(0, int(input())):
	(n, m) = map(int, input().split(' '))
	if n % 2 == 0:
		if m >= n - 1 and m <= n * (n + 1) / 2:
			if n == 2:
				if m == 1:
					print(1)
				else:
					print(2)
			elif m <= n + 1:
				print(2)
			elif m <= 2 * n:
				print(3)
			elif (m - 2 * n) % (n / 2) == 0:
				print(int(3 + (m - 2 * n) // (n / 2)))
			else:
				print(int(3 + (m - 2 * n) // (n / 2) + 1))
		else:
			print(-1)
	elif n == 1:
		if m == 1:
			print(1)
		elif m == 0:
			print(0)
		else:
			print(-1)
	elif m >= n - 1 and m <= n * (n + 1) / 2:
		if m <= n + 1:
			print(2)
		elif m <= n * 2:
			print(3)
		elif (m - 2 * n) % n == 0:
			print(int(3 + 2 * ((m - 2 * n) // n)))
		elif (m - 2 * n) % n <= n // 2:
			print(int(3 + 2 * ((m - 2 * n) // n) + 1))
		else:
			print(int(3 + 2 * ((m - 2 * n) // n) + 2))
	else:
		print(-1)


import math
for _ in range(int(input())):
	(N, M) = map(int, input().split())
	maxi = int(N * (N - 1) / 2) + N
	if N == 1 and M == 0:
		print(0)
	elif M < N - 1 or M > maxi or M == 0:
		print(-1)
	elif M == 1 and N == 1:
		print(1)
	elif M == 1 and N == 2:
		print(1)
	elif M == N - 1 or M == N + 1 or M == N:
		print(2)
	elif M > N + 1 and M <= 2 * N:
		print(3)
	elif N % 2 != 0:
		i = M // N
		dec = i + 0.5
		act = M / N
		if act >= dec:
			ans = math.ceil(M / N) + i
			print(ans)
		else:
			ans = math.ceil(M / N) + (i - 1)
			print(ans)
	else:
		i = M // N
		dec = i + 0.5
		act = M / N
		if act > dec:
			ans = math.ceil(M / N) + i
			print(ans)
		else:
			ans = math.ceil(M / N) + (i - 1)
			print(ans)


def ge(n, deg):
	if deg == 2:
		return n + 1
	else:
		return n + (deg - 1) * n // 2
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if m >= n - 1 and m <= n * (n + 1) // 2:
		if n <= 2 and m <= 1:
			print(m)
		else:
			(l, r) = (2, n + 1)
			while l <= r:
				deg = (l + r) // 2
				if ge(n, deg) >= m:
					r = deg - 1
				else:
					l = deg + 1
			print(l)
	else:
		print('-1')