A clique in a graph is set of nodes such that there is an edge between any two distinct nodes in the set. Finding the largest clique in a graph is a computationally difficult problem. Currently no polynomial time algorithm  is known for solving this. However, you wonder what is the minimum size of the largest clique in any graph with $n$ nodes and $m$ edges.  

For example, consider a graph with $n=4$ nodes and $m=5$ edges.  The graph below shows $4$ nodes with $4$ edges and no cliques.  It is evident that the addition of any $5^{th}$ edge must create two cliques with $3$ members each.  

Input Format

The first line contains an integer $\boldsymbol{\boldsymbol{t}}$, the number of test cases.  

Each of the next $\boldsymbol{\boldsymbol{t}}$ lines contains two space-separated integers $n$ and $m$.  

Constraints

$1\leq t\leq100000$  
$2\leq n\leq10000$  
$1\leq m\leq\frac{n\times(n-1)}{2}$

Output Format

For each test case, print the minimum size of the largest clique that must be formed given $n$ and $m$.   

Sample Input
3  
3 2  
4 6  
5 7

Sample Output
2  
4  
3

Explanation

For the first case, we have two cliques with two nodes each:  

For the second test case, the only valid graph having $4$ nodes and $\boldsymbol{6}$ edges is one where each pair of nodes is connected. So the size of the largest clique cannot be smaller than $4$.  

For the third test case, it is easy to verify that any graph with $5$ nodes and $7$.  The $5$ solid lines in the graph below indicate the maximum edges that can be added without forming a clique larger than $2$.  The dashed lines could connect any two nodes not connected by solid lines producing a clique of size $3$.  

Hints 
Turan's theorem gives us an upper bound on the number of edges a graph can have if we wish that it should not have a clique of size $\boldsymbol{x}$. Though the bound is not exact, it is easy to extend the statement of the theorem to get an exact bound in terms of $n$ and $\boldsymbol{x}$. Once this is done, we can binary search for the largest $\boldsymbol{x}$ such that $f(n,x)<=m$. See: Turan's Theorem

Difficulty: MEDIUM
Tags: Graph algorithms

Starter code:

Solutions:
import math

def s1(n, m):
	ga = n % m
	gb = m - ga
	sa = n // m + 1
	sb = n // m
	return ga * gb * sa * sb + ga * (ga - 1) * sa * sa // 2 + gb * (gb - 1) * sb * sb // 2

def s(n, c):
	l = 1
	h = n + 1
	while l + 1 < h:
		m = l + (h - l) // 2
		k = s1(n, m)
		if k < c:
			l = m
		else:
			h = m
	return h
t = int(input())
for i in range(t):
	(n, m) = [int(j) for j in input().split()]
	print(s(n, m))


import math

def s1(n, m):
	ga = n % m
	gb = m - ga
	sa = n // m + 1
	sb = n // m
	return ga * gb * sa * sb + ga * (ga - 1) * sa * sa // 2 + gb * (gb - 1) * sb * sb // 2

def s(n, c):
	l = 1
	h = n + 1
	while l + 1 < h:
		m = l + (h - l) // 2
		k = s1(n, m)
		if k < c:
			l = m
		else:
			h = m
	return h
t = int(input())
for i in range(t):
	(n, m) = [int(j) for j in input().split()]
	print(s(n, m))


import math

def byTuransTheorem(n, r):
	nmodr = n % r
	size_nmodr = int(math.ceil(n / r))
	r_nmodr = r - nmodr
	size_r_nmodr = int(math.floor(n / r))
	return int((n * n - nmodr * size_nmodr * size_nmodr - r_nmodr * size_r_nmodr * size_r_nmodr) / 2)

def solve(n, e):
	low = 1
	high = n + 1
	while low + 1 < high:
		mid = low + (high - low) // 2
		k = byTuransTheorem(n, mid)
		if k < e:
			low = mid
		else:
			high = mid
	return high

def main():
	T = int(input())
	while T > 0:
		(vertices, edges) = [int(x) for x in input().split()]
		print(solve(vertices, edges))
		T = T - 1
main()


def turan(n, r):
	g1 = n % r
	g2 = r - g1
	sz1 = int(n / r) + 1
	sz2 = int(n / r)
	return int(g1 * sz1 * g2 * sz2 + g1 * (g1 - 1) * sz1 * sz1 / 2 + g2 * (g2 - 1) * sz2 * sz2 / 2)
T = int(input())
for t in range(T):
	(N, M) = (int(c) for c in input().split())
	(lo, hi) = (1, N + 1)
	while lo + 1 < hi:
		mid = lo + int((hi - lo) / 2)
		candidate = turan(N, mid)
		if candidate < M:
			lo = mid
		else:
			hi = mid
	print(hi)


import sys
__author__ = 'bbyk'

def e_for_complete(n):
	return n * (n - 1) >> 1

def edges_at_most(r, n):
	m = n // r
	k = n % r
	rk = r - k
	res = e_for_complete(k) * (m + 1) * (m + 1)
	res += e_for_complete(rk) * m * m
	res += k * (m + 1) * rk * m
	return res

def min_max_clique(N, M):
	l = 2
	r = N
	while l < r:
		m = l + (r - l >> 1)
		n_edges = edges_at_most(m, N)
		if n_edges == M:
			return m
		if n_edges > M:
			r = m
		else:
			l = m + 1
	return r
cin = None
if len(sys.argv) > 1:
	cin = open(sys.argv[1])
else:
	cin = sys.stdin
T = int(cin.readline())
while T:
	(N, M) = [int(t) for t in cin.readline().split(' ', 1)]
	print(min_max_clique(N, M))
	T -= 1
if cin is not sys.stdin:
	cin.close()


import sys
import math

def Turan(n, r):
	a1 = n % r
	a2 = math.ceil(n / r)
	a3 = math.floor(n / r)
	return int((n * n - a1 * a2 * a2 - (r - a1) * a3 * a3) / 2)
for i in range(int(sys.stdin.readline())):
	(v, e) = [int(elem) for elem in sys.stdin.readline().split()]
	Min = 1
	Max = v
	NotFound = True
	while NotFound:
		Mid = math.floor((Max + Min) / 2)
		if Turan(v, Mid) < e:
			Min = Mid
		else:
			Max = Mid
		if math.floor((Max + Min) / 2) == Mid:
			NotFound = False
	print(Mid + 1)


def clique(nodes, edges):
	low = 2
	high = nodes

	def max_edges_for_clique_size(n):
		mod = nodes % n
		base = n - mod
		base_size = nodes // n
		big_size = base_size + 1
		big_count = mod * (mod - 1) * big_size * big_size / 2
		base_count = base * (base - 1) * base_size * base_size / 2
		return big_count + base_count + base_size * base * big_size * mod
	while low < high:
		mid = low + (high - low) // 2
		edges_for_mid = max_edges_for_clique_size(mid)
		if edges_for_mid == edges:
			return mid
		if edges_for_mid < edges:
			low = mid + 1
		else:
			high = mid
	return high
t = int(input())
while t:
	try:
		(n, m) = [int(value) for value in input().split()]
	except EOFError:
		pass
	print(clique(n, m))
	t -= 1


def max_edges(n, k):
	s = n // k
	r = n % k
	return (k - r) * (k - r - 1) * s * s // 2 + r * (r - 1) * (s + 1) * (s + 1) // 2 + (k - r) * r * s * (s + 1)
for _ in range(int(input())):
	[n, m] = list(map(int, input().split()))
	mini = 1
	maxi = n + 1
	while maxi - mini > 1:
		midi = (maxi + mini) // 2
		if max_edges(n, midi) >= m:
			maxi = midi
		else:
			mini = midi
	print(mini + 1)


from fractions import Fraction
from math import *

def comp_T_approx(r, n):
	return Fraction((r - 1) * n ** 2, 2 * r)

def comp_T(r, n):
	h_1 = N % r
	h_2 = r - h_1
	s_1 = int(N / r) + 1
	s_2 = s_1 - 1
	return s_2 ** 2 * (h_2 * (h_2 - 1)) / 2 + s_1 * s_2 * h_1 * h_2 + s_1 ** 2 * (h_1 * (h_1 - 1)) / 2
T = int(input())
for i in range(T):
	D = list(map(int, input().split()))
	N = D[0]
	M = D[1]
	x = Fraction(2 * M, N ** 2)
	k = Fraction(1, 1 - x)
	for r in range(int(k), N + 1):
		t = comp_T(r, N)
		if t >= M:
			print(r)
			break


from math import ceil
T = int(input())

def solve(n, m):
	hi = n
	lo = 1
	while hi > lo + 1:
		mid = (hi + lo) // 2
		if sz(n, mid) >= m:
			hi = mid
		else:
			lo = mid
	return hi

def sz(n, r):
	return 0.5 * (n ** 2 - n % r * ceil(n / r) ** 2 - (r - n % r) * (n // r) ** 2)
for t in range(T):
	(n, m) = [int(_) for _ in input().split()]
	print(solve(n, m))


def clique(N, M):
	low = 1
	high = N + 1

	def calculate(N, K):
		g1 = N % K
		g2 = K - g1
		sz2 = N // K
		sz1 = sz2 + 1
		return g1 * sz1 * g2 * sz2 + g1 * (g1 - 1) * sz1 * sz1 / 2 + g2 * (g2 - 1) * sz2 * sz2 / 2
	while low + 1 < high:
		mid = low + (high - low) // 2
		if calculate(N, mid) < M:
			low = mid
		else:
			high = mid
	return high

def main():
	T = int(input())
	for _ in range(T):
		(N, M) = [int(i) for i in input().split()]
		print(clique(N, M))
main()


import sys
import math
num_tests = int(sys.stdin.readline().strip())
for _ in range(0, num_tests):
	(n, e) = map(lambda x: float(x), sys.stdin.readline().strip().split())
	r_limit = math.floor(1 / (1 - 2 * e / n ** 2))

	def max_edge(n, r):
		n_mod_r = n % r
		return 0.5 * (n * n - n_mod_r * math.ceil(n / r) ** 2 - (r - n_mod_r) * math.floor(n / r) ** 2)
	while max_edge(n, r_limit) < e:
		r_limit += 1
	print(int(r_limit))


def s1(n, m):
	ga = n % m
	gb = m - ga
	sa = n // m + 1
	sb = n // m
	return ga * gb * sa * sb + ga * (ga - 1) * sa * sa // 2 + gb * (gb - 1) * sb * sb // 2

def s(n, c):
	l = 1
	h = n + 1
	while l + 1 < h:
		m = l + (h - l) // 2
		k = s1(n, m)
		if k < c:
			l = m
		else:
			h = m
	return h
t = int(input())
for i in range(t):
	(n, m) = [int(j) for j in input().split()]
	print(s(n, m))


from sys import stdin
t = int(stdin.readline().strip())

def turin2(n, e, r):
	base = int(n / r)
	higher = n - base * r
	edges_required = 0
	edges_required += higher * (base + 1) * (n - base - 1)
	edges_required += (r - higher) * base * (n - base)
	edges_required /= 2
	return e > edges_required

def turin(n, e):
	r = int(1 / (1 - 2 * e / (n * n)) - 1)
	if r < 1:
		r = 1
	while turin2(n, e, r):
		r += 1
	return r
for i in range(t):
	(n, m) = tuple([int(i) for i in stdin.readline().strip().split()])
	print(turin(n, m))


def s1(n, m):
	ga = n % m
	gb = m - ga
	sa = n // m + 1
	sb = n // m
	return ga * gb * sa * sb + ga * (ga - 1) * sa * sa // 2 + gb * (gb - 1) * sb * sb // 2

def s(n, c):
	l = 1
	h = n + 1
	while l + 1 < h:
		m = l + (h - l) // 2
		k = s1(n, m)
		if k < c:
			l = m
		else:
			h = m
	return h
t = int(input())
for i in range(t):
	(n, m) = [int(j) for j in input().split()]
	print(s(n, m))


from math import *

def g(n, r):
	a = ceil(n / r)
	b = floor(n / r)
	return (n * n - n % r * a * a - (r - n % r) * b * b) / 2
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	if 2 * (m - n * n) % (2 * m - n * n) == 0:
		r = 2 * (n * n - m) // (n * n - 2 * m) - 1
	else:
		r = 2 * (n * n - m) // (n * n - 2 * m)
	while g(n, r) <= m and g(n, r + 1) != g(n, r):
		r += 1
	while r > 0 and g(n, r - 1) >= m and (g(n, r - 1) != g(n, r)):
		r -= 1
	print(r)


from math import *

def T(n, r):
	r = float(r)
	a = pow(ceil(n / r), 2)
	b = pow(floor(n / r), 2)
	c = n % r
	ans = 1 / 2 * (n * n - c * a - r * b + c * b)
	return ans
t = int(input())
for i in range(t):
	l = input()
	(n, m) = [int(x) for x in l.split()]
	done = 0
	l = 1
	h = n
	while h - l > 1:
		r = floor((l + h) / 2)
		Tr = T(n, r)
		if Tr < m:
			l = r
		elif Tr > m:
			h = r
		else:
			l = r
			h = r
	ans = h
	if m == T(n, l):
		ans = l
	print(ans)


import math

def s1(n, m):
	ga = n % m
	gb = m - ga
	sa = n // m + 1
	sb = n // m
	return ga * gb * sa * sb + ga * (ga - 1) * sa * sa // 2 + gb * (gb - 1) * sb * sb // 2

def s(n, c):
	l = 1
	h = n + 1
	while l + 1 < h:
		m = l + (h - l) // 2
		k = s1(n, m)
		if k < c:
			l = m
		else:
			h = m
	return h
t = int(input())
for i in range(t):
	(n, m) = [int(j) for j in input().split()]
	print(s(n, m))


import math

def turanMax(n, x):
	(d1, x2) = divmod(n, x)
	d2 = d1 + 1
	x1 = x - x2
	m = d2 * d1 * x2 * x1 + d2 ** 2 * (x2 ** 2 - x2) / 2 + d1 ** 2 * (x1 ** 2 - x1) / 2
	return m
T = int(input())
for t in range(T):
	(N, M) = map(int, input().split())
	maxx = M + 1
	minx = 2
	X = 0
	while maxx != minx:
		X = math.ceil((maxx + minx) / 2)
		if turanMax(N, X - 1) < M:
			minx = X
		else:
			maxx = X - 1
	print(maxx)


import math
T = int(input())
for t in range(T):
	(N, M) = map(int, input().split())
	(lo, hi) = (1, N)
	while lo < hi:
		mid = (lo + hi) // 2
		edges = 0.5 * (N ** 2 - N % mid * math.ceil(N / mid) ** 2 - (mid - N % mid) * math.floor(N / mid) ** 2)
		if edges < M:
			lo = mid + 1
		else:
			hi = mid
	print(lo)


import math

def turan_graph(n, r):
	return (n ** 2 - n % r * math.ceil(n / r) ** 2 - (r - n % r) * (n // r) ** 2) // 2
t = int(input().strip())
for _ in range(t):
	(n, m) = (int(x) for x in input().strip().split(' '))
	low = 1
	high = n + 1
	while low + 1 < high:
		mid = low + (high - low) // 2
		k = turan_graph(n, mid)
		if k < m:
			low = mid
		else:
			high = mid
	print(high)


from math import ceil, floor

def TulanEdge(n, r):
	firstPart = n % r * ceil(n / r) ** 2
	secondPart = (r - n % r) * floor(n / r) ** 2
	return int(0.5 * (n ** 2 - firstPart - secondPart))

def getMinR(n, m):
	return int(floor(n ** 2 / (n ** 2 - 2 * m)))
T = int(input())
for _ in range(T):
	(N, M) = tuple(map(int, input().split()))
	minR = getMinR(N, M)
	result = minR
	for r in range(minR, N + 1):
		curTulanEdge = TulanEdge(N, r)
		if M <= curTulanEdge:
			result = r
			break
	print(result)


from bisect import bisect_left
from math import floor, ceil

def turan(n, r):
	return 1 / 2 * (n ** 2 - n % r * ceil(n / r) ** 2 - (r - n % r) * floor(n / r) ** 2)
for q in range(int(input())):
	(n, E) = tuple(map(int, input().split()))
	i = n // 2
	hi = n
	lo = 1
	while lo < hi:
		if turan(n, i) < E:
			if i == n or turan(n, i + 1) >= E:
				print(i + 1)
				break
			lo = i + 1
			i += max((hi - lo) // 2, 1)
		elif turan(n, i) >= E:
			if i == 1 or turan(n, i - 1) < E:
				print(i)
				break
			hi = i - 1
			i -= max((hi - lo) // 2, 1)


import math

def f(n, r):
	if r != 1:
		n2 = n * n
		nmr = n % r
		return 0.5 * (n2 - nmr * math.ceil(n / r) ** 2 - (r - nmr) * math.floor(n / r) ** 2)
	else:
		return 1

def binary(n, m):
	low = 1
	high = n
	if f(n, n) <= m:
		return n
	while low + 1 < high:
		mid = int((low + high) / 2)
		r = f(n, mid)
		if r < m:
			low = mid
		else:
			high = mid
	return high
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	r = binary(n, m)
	if r < n and f(n, r + 1) <= m:
		r = r + 1
	if r < n and f(n, r + 1) <= m:
		r = r + 1
	print(r)


def turan(n, r):
	nr_c = (n - 1) // r + 1
	nr_f = n // r
	nmr = n % r
	return (n * n - nmr * nr_c * nr_c - (r - nmr) * nr_f * nr_f) // 2
t = int(input())
for i in range(t):
	[n, m] = [int(x) for x in input().split()]
	res = -1
	l = 1
	r = n + 1
	while l < r:
		mid = (l + r) // 2
		cur = turan(n, mid)
		if cur < m:
			l = mid + 1
		else:
			res = mid
			r = mid
	print(res)


import math

def max_filled(n, clique_size):
	if clique_size <= 1:
		return 0
	r = clique_size
	return 1 / 2 * (n ** 2 - n % r * math.ceil(n / r) ** 2 - (r - n % r) * math.floor(n / r) ** 2)

def min_filled(n, clique_size):
	if clique_size <= 1:
		return 0
	return math.floor(max_filled(n, clique_size - 1) + 1)

def search(n, m, lo, hi):
	if hi == lo + 1:
		return lo
	mid = (hi + lo) // 2
	m_min = min_filled(n, mid)
	if m_min > m:
		return search(n, m, lo, mid)
	m_max = max_filled(n, mid)
	if m_max < m:
		return search(n, m, mid, hi)
	return mid

def min_clique(n, m):
	return search(n, m, 1, n + 1)
t = int(input())
for _ in range(t):
	(n, m) = (int(s) for s in input().strip().split())
	print(min_clique(n, m))


input_fn = input

def get_int():
	return int(input_fn())

def get_int_list():
	return [int(i) for i in input_fn().split()]

def turan(n, r):
	import math
	(ceil, floor) = (int(math.ceil(n / r)), int(math.floor(n / r)))
	mod = n % r
	return (n * n - mod * ceil * ceil - (r - mod) * floor * floor) / 2

def solve(n, m):

	def _solve(lo, hi):
		if hi <= lo + 1:
			return lo
		k = (lo + hi) // 2
		if m > turan(n, k - 1):
			return _solve(k, hi)
		return _solve(lo, k)
	print(_solve(2, n + 1))

def main():
	for _ in range(get_int()):
		(n, m) = get_int_list()
		solve(n, m)
main()


from math import ceil, floor

def get_accurate_edges(nodes, clique_guess):
	nodes = int(nodes)
	clique_guess = int(clique_guess)
	calc_edges = (nodes ** 2 - nodes % clique_guess * ceil(nodes / clique_guess) ** 2 - (clique_guess - nodes % clique_guess) * (nodes // clique_guess) ** 2) // 2
	return calc_edges

def get_result(nodes, edges):
	k = 1.0 / (1.0 - 2.0 * edges / (1.0 * nodes ** 2))
	clique_guess = max(min(nodes, ceil(k)) - 3, 1)
	while clique_guess < nodes and edges > get_accurate_edges(nodes, clique_guess):
		clique_guess += 1
	return int(clique_guess)

def main():
	cases = int(input())
	for i in range(cases):
		in_str = input()
		(nodes, edges) = [int(i) for i in in_str.strip().split()]
		print(get_result(nodes, edges))

def get_int_list(in_str):
	return [int(i) for i in in_str.strip().split()]
main()


import math
nedge = lambda n, r: (pow(n, 2) - n % r * pow(math.ceil(n / r), 2) - (r - n % r) * pow(math.floor(n / r), 2)) / 2
l = int(input())
for i in range(l):
	tmp = input().split(' ')
	n = int(tmp[0])
	m = int(tmp[1])
	r = math.ceil(1 / (1 - 2 * m / pow(n, 2)))
	while nedge(n, r) < m:
		r += 1
	while nedge(n, r - 1) >= m:
		r -= 1
	print(r)


import math

def Turan_max(v, n):
	r = v % (n - 1)
	edges = (n - 2) * (v * v - r * r) / (2 * n - 2)
	if r > 1:
		edges += r * (r - 1) / 2
	return edges

def min_R(V, E):
	n = V * V // (V * V - 2 * E) - 1
	if n < 2:
		n = 2
	return n

def find_turan_max(V, E):
	n = min_R(V, E)
	while True:
		ev = Turan_max(V, n)
		if ev >= E:
			return n - 1
		n += 1
t = int(input().strip())
for a0 in range(t):
	n_m = [int(a_temp) for a_temp in input().strip().split(' ')]
	print(find_turan_max(n_m[0], n_m[1]))


from math import floor

def choose2(n):
	return int(n * (n - 1) / 2)

def mustHaveClique(n, m, r):
	if r > n:
		return False
	elif r <= 1:
		return True
	elif r == 2 and m > 0:
		return True
	elif r >= 2 and m <= 0:
		return False
	numBigGroups = n % (r - 1)
	numSmallGroups = r - 1 - numBigGroups
	sizeBigGroup = int(floor(n / (r - 1))) + 1
	sizeSmallGroup = sizeBigGroup - 1
	numEdges = choose2(numBigGroups) * sizeBigGroup ** 2 + choose2(numSmallGroups) * sizeSmallGroup ** 2 + numBigGroups * numSmallGroups * (sizeBigGroup * sizeSmallGroup)
	return m > numEdges

def findBiggestR(n, m):
	if n <= 0:
		return 0
	lo = 0
	hi = n + 1
	while hi - lo > 1:
		mid = floor((lo + hi) / 2)
		if mustHaveClique(n, m, mid):
			lo = mid
		else:
			hi = mid
	return lo
T = int(input().strip())
for testcounter in range(T):
	(N, M) = [int(a) for a in input().strip().split()]
	print(findBiggestR(N, M))


import sys
import math
handle = sys.stdin
T = int(handle.readline().strip())

def TG(n, r):
	return 1 / 2 * (n ** 2 - n % r * math.ceil(n / r) ** 2 - (r - n % r) * math.floor(n / r) ** 2)

def Solve(N, M):
	r = math.ceil(N ** 2 / (N ** 2 - 2 * M))
	while True:
		if TG(N, r) < M:
			r += 1
		else:
			break
	return r
for t in range(T):
	(N, M) = handle.readline().strip().split(' ')
	(N, M) = [int(N), int(M)]
	res = Solve(N, M)
	print(res)


import sys
from math import ceil, floor
T = int(input().strip())

def Turan(r, N):
	val = (1 - 1 / r) * n ** 2 / 2
	return val

def Mstar(r, N):
	val = 0.5 * (N ** 2 - N % r * ceil(N / r) ** 2 - (r - N % r) * floor(N / r) ** 2)
	return val

def binarySearch(M, N):
	r = N
	search = True
	lower_bound = 0
	upper_bound = N
	while search:
		if Mstar(r - 1, N) < M and Mstar(r, N) >= M:
			search = False
			break
		if Mstar(r, N) < M and Mstar(r + 1, N) >= M:
			search = False
			r = r + 1
			break
		if M < Mstar(r, N):
			if r < upper_bound:
				upper_bound = r
		elif r > lower_bound:
			lower_bound = r
		r = round((upper_bound + lower_bound) / 2)
	return r
for i in range(T):
	(N, M) = [int(q_temp) for q_temp in input().strip().split(' ')]
	val = binarySearch(M, N)
	print(val)


import math
tries = int(input())
for _ in range(tries):
	nm = [float(i) for i in input().split()]
	(n, m) = (nm[0], nm[1])
	r = int(math.ceil(n ** 2 / (n ** 2 - 2 * m)))
	while (n ** 2 - n % r * math.ceil(n / r) ** 2 - (r - n % r) * math.floor(n / r) ** 2) / 2 < m:
		r += 1
	print(r)


import math

def turan_m(n, r):
	return 0.5 * (n ** 2 - n % r * math.ceil(n / r) ** 2 - (r - n % r) * math.floor(n / r) ** 2)

def minimum_clique(n, m):
	first = 1
	last = n - 1
	found = False
	while first <= last and (not found):
		i = first + (last - first) // 2
		current = turan_m(n, i)
		following = turan_m(n, i + 1)
		if current < m and (i == n - 1 or following >= m):
			found = True
		elif current < m:
			first = i + 1
		else:
			last = i - 1
	return i + 1
t = int(input())
for _ in range(t):
	(n, m) = [int(x) for x in input().split()]
	print(minimum_clique(n, m))


import math

def ss(n, r):
	return (n ** 2 - n % r * math.ceil(n / r) ** 2 - (r - n % r) * math.floor(n / r) ** 2) / 2
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	r = n - 1
	while r > 1:
		if ss(n, r // 2) > m:
			r = r // 2
		else:
			break
	while r > 1:
		mm = ss(n, r)
		if m > mm:
			break
		r -= 1
	print(r + 1)


import math
t = int(input().strip())
turin = lambda n, r: int(1 / 2 * (n ** 2 - n % r * math.ceil(n / r) ** 2 - (r - n % r) * math.floor(n / r) ** 2))
for _ in range(t):
	(n, m) = list(map(int, input().strip().split()))
	bottom = 1
	top = guess = n
	f = turin(n, guess)
	while f != m:
		if f > m:
			top = guess
		else:
			bottom = guess
		if guess == math.ceil((top + bottom) / 2):
			break
		else:
			guess = math.ceil((top + bottom) / 2)
			f = turin(n, guess)
	print(guess)


import sys
import math

def Turan(n, r):
	if r == 0:
		return 0
	res = n * n - n % r * math.ceil(n / r) ** 2 - (r - n % r) * math.floor(n / r) ** 2
	res //= 2
	return res

def find_smallest_cq(n, m):
	if m == 0:
		return 1
	if m <= n - 1:
		return 2
	if m == n * (n - 1) / 2:
		return n
	(left, right) = (1, n)
	while left <= right:
		mid = (left + right) // 2
		tmid = Turan(n, mid)
		if tmid == m:
			return mid
		if tmid > m:
			right = mid - 1
		else:
			left = mid + 1
	if tmid > m:
		return mid
	else:
		return mid + 1
t = int(input().strip())
for i in range(t):
	(n, m) = map(int, input().strip().split(' '))
	print(find_smallest_cq(n, m))


def main():
	T = readints()[0]
	for i in range(0, T):
		(N, M) = readints()
		print(binary_search(1, N, M, N))

def readints():
	return [int(fld) for fld in input().split()]

def binary_search(start, end, M, N):
	mid = int((start + end) / 2)
	if end == start:
		return end
	if (end - start == 1) & (turan_theorem(N, end) >= M) & (turan_theorem(N, start) < M):
		return end
	elif (end - start == 1) & (turan_theorem(N, end) < M):
		return start
	if turan_theorem(N, mid) < M:
		return binary_search(mid, end, M, N)
	else:
		return binary_search(start, mid, M, N)

def turan_theorem(N, clique):
	c = clique
	r = N % clique
	n = int(N / clique)
	max_num_of_edges = N * (N - 1) / 2 - (c - r) * n * (n - 1) / 2 - r * (n + 1) * n / 2
	return max_num_of_edges
main()


def calculate(x, n):
	mod = n % x
	g2 = x - mod
	up = n // x + 1
	dn = n // x
	up_2 = up * up
	dn_2 = dn * dn
	return (n * n - mod * up_2 - (x - mod) * dn_2) // 2

def find_largest_possible_clique(n, m):
	a = 0
	z = n + 1
	while a + 1 < z:
		x = (a + z) // 2
		if calculate(x, n) < m:
			a = x
		else:
			z = x
	return z

def main():
	t = int(input().strip())
	for i in range(t):
		(n, m) = list(map(int, input().strip().split()))
		print(find_largest_possible_clique(n, m))
main()


def turan(n, r):
	mod = n % r
	floor = n // r
	return int(0.5 * (n * n - mod * (floor + 1) * (floor + 1) - (r - mod) * floor * floor))

def find_r_binary(n, m, rmin, rmax):
	if rmin == rmax:
		return rmin
	r = (rmax - rmin) // 2 + rmin
	t = turan(n, r)
	if m == t:
		return r
	elif m > t:
		return find_r_binary(n, m, r + 1, rmax)
	return find_r_binary(n, m, rmin, r)
import sys
t = int(sys.stdin.readline())
while t > 0:
	t -= 1
	(n, m) = (int(x) for x in sys.stdin.readline().split())
	print(find_r_binary(n, m, 2, n))


import math

def s1(n, m):
	ga = n % m
	gb = m - ga
	sa = n // m + 1
	sb = n // m
	return ga * gb * sa * sb + ga * (ga - 1) * sa * sa // 2 + gb * (gb - 1) * sb * sb // 2

def s(n, c):
	l = 1
	h = n + 1
	while l + 1 < h:
		m = l + (h - l) // 2
		k = s1(n, m)
		if k < c:
			l = m
		else:
			h = m
	return h
t = int(input())
for i in range(t):
	(n, m) = [int(j) for j in input().split()]
	print(s(n, m))


import math

def turan(n, r):
	fca = pow(math.ceil(n / r), 2)
	fcb = pow(math.floor(n / r), 2)
	return 0.5 * (pow(n, 2) - n % r * fca - (r - n % r) * fcb)
for _ in range(int(input())):
	(V, E) = map(int, input().split())
	low = 1
	high = V
	while low + 1 < high:
		mid = (low + high) // 2
		tedges = int(turan(V, mid))
		if tedges < E:
			low = mid
		else:
			high = mid
	print(high)


import math

def turan(n, r):
	return 1 / 2 * (n * n - n % r * math.ceil(n / r) ** 2 - (r - n % r) * math.floor(n / r) ** 2)
T = int(input().strip())
for t in range(T):
	(n, m) = map(int, input().strip().split(' '))
	low = 1
	high = n - 1
	r = (high + low) // 2
	while high >= low:
		if turan(n, r) < m:
			low = r + 1
		else:
			high = r - 1
		r = (high + low) // 2
	print(r + 1)


from math import floor, ceil

def turan(N, k):
	return (N ** 2 - N % k * ceil(N / k) ** 2 - (k - N % k) * floor(N / k) ** 2) / 2
T = int(input())
for _ in range(T):
	(N, M) = [int(x) for x in input().split()]
	lo = 1
	hi = N
	while lo < hi:
		k = (hi + lo) // 2
		if M > turan(N, k):
			lo = k + 1
		else:
			hi = k
	print(lo)


import sys
from math import *

def Turan(n, r):
	return floor((n ** 2 - n % r * ceil(n / r) ** 2 - (r - n % r) * (n // r) ** 2) / 2)
t = int(input())
for a0 in range(t):
	(n, m) = input().strip().split()
	(n, m) = (int(n), int(m))
	low = 0
	high = n
	while low + 1 < high:
		mid = (low + high) // 2
		r = Turan(n, mid)
		if r < m:
			low = mid
		else:
			high = mid
	print(high)


from math import floor
from math import ceil

def t(n, k):
	fr = floor(float(n) / k)
	cr = ceil(float(n) / k)
	A = n * n
	B = n % k * (cr * cr)
	C = (k - n % k) * (fr * fr)
	return (A - B - C) / 2

def kUpperBound(m, n):
	return ceil(1 / (1 - 2 * m / (n * n)))

def searchForK(m, n):
	upper = n
	lower = 1
	while upper > lower + 1:
		kmid = lower + (upper - lower) // 2
		edges = t(n, kmid)
		if edges == m:
			return kmid
		elif edges < m:
			lower = kmid
		elif edges > m:
			upper = kmid
	return upper
T = int(input())
for i in range(T):
	(n, m) = map(int, input().split())
	k = searchForK(m, n)
	print(k)


import sys

def getM(n, k):
	h = n // k
	if h != 0:
		b = n - k * h
		a = k * (1 + h) - n
	else:
		b = n
		a = 0
	return (h + 1) * ((h + 1) * b * (b - 1) / 2 + b * a * h) + h ** 2 * a * (a - 1) / 2
T = int(sys.stdin.readline())
IN = []
for j in range(T):
	IN.append([int(a) for a in sys.stdin.readline().split()])
for i in range(T):
	(n, m) = IN[i]
	if n == 1 and m == 0:
		print(1)
		continue
	elif n == 2 and m == 1:
		print(2)
		continue
	k = 2 * (n ** 2 - m) // (n ** 2 - 2 * m)
	if (k - 2) * n ** 2 // (2 * (k - 1)) == (k - 2) * n ** 2 / (2 * (k - 1)):
		k = k - 1
	while getM(n, k) < m:
		k += 1
	if n >= 2 and k == 1:
		k = 2
	print(k)


import math

def edge(n, k):
	e = n * n
	e -= n % k * int(math.ceil(n / k)) ** 2
	e -= (k - n % k) * int(math.floor(n / k)) ** 2
	return e >> 1
for q in range(int(input().strip())):
	(n, m) = map(int, input().strip().split())
	if m + m == n * (n - 1):
		print(n)
		continue
	k = int(1 / (1 - 2 * m / n / n))
	while edge(n, k) < m:
		k += 1
	print(k)


import math
t = int(input())
f1 = lambda n, r: 0.5 * (n ** 2 - n % r * math.ceil(n / r) ** 2 - (r - n % r) * math.floor(n / r) ** 2)
f2 = lambda n, r: 0.5 * (1 - 1 / r) * n ** 2
arr = []
for j in range(t):
	(n, m) = list(map(int, input().split()))
	first = 1
	last = n
	r = (first + last) // 2
	l = f1(n, r)
	u = f2(n, r)
	while True:
		if l <= m:
			if l == m:
				print(r)
				break
			elif u <= m and f1(n, r + 1) > m:
				print(r + 1)
				break
			elif u > m and f1(n, r + 1) > m:
				print(r + 1)
				break
		if m >= l:
			first = r + 1
		else:
			last = r - 1
		r = (first + last) // 2
		l = f1(n, r)
		u = f2(n, r)


import math

def turan(n, k):
	a = n ** 2 - n % k * math.ceil(n / k) ** 2
	b = (k - n % k) * math.floor(n / k) ** 2
	return 0.5 * (a - b)
T = int(input())
for i in range(T):
	[n, m] = list(map(int, input().split()))
	l = 2
	r = n - 1
	while l <= r:
		mid = int((l + r) / 2)
		t = turan(n, mid)
		if m > t:
			l = mid + 1
		else:
			r = mid - 1
	print(l)


import math

def exact(n, k):
	return (n * n - n % k * math.ceil(n / k) ** 2 - (k - n % k) * math.floor(n / k) ** 2) / 2
for case in range(int(input())):
	(N, M) = map(int, input().split())
	k = math.ceil(N * N / (N * N - 2 * M))
	while M > exact(N, k):
		k += 1
	print(k)


from math import ceil, floor
for _ in range(int(input())):
	(n, m) = (int(x) for x in input().split())
	res = lo = 2
	hi = n
	while lo <= hi:
		r = (lo + hi) // 2
		c = n % r * ceil(n / r) ** 2
		f = (r - n % r) * floor(n / r) ** 2
		e = int(0.5 * (n ** 2 - c - f))
		if e <= m:
			res = r + (e < m)
			lo = r + 1
		else:
			hi = r - 1
	print(res)


from math import ceil, floor

def f(n, r):
	return (n * n - n % r * ceil(n / r) ** 2 - (r - n % r) * floor(n / r) ** 2) // 2

def solve(n, m):
	l = 1
	u = n + 1
	while u - l > 1:
		mid = (u + l) // 2
		if f(n, mid) < m:
			l = mid
		else:
			u = mid
	return u

def main():
	t = int(input().strip())
	for ti in range(t):
		(n, m) = [int(x) for x in input().strip().split()]
		answer = solve(n, m)
		print(answer)
main()


import math

def f_exact(n, r):
	return (n ** 2 - n % r * math.ceil(n / r) ** 2 - (r - n % r) * math.floor(n / r) ** 2) // 2

def calculate(N, M):
	(l, h) = (1, N - 1)
	while l <= h:
		m = l + (h - l) // 2
		edges = f_exact(N, m)
		if edges == M:
			return m
		if edges < M:
			l = m + 1
		else:
			h = m - 1
	return l
T = int(input())
for t in range(T):
	(N, M) = [int(i) for i in input().split()]
	print(calculate(N, M))


import math
t = int(input())

def compute_edges(n, r):
	n_mod_r = n % r
	return (n ** 2 - n_mod_r * math.ceil(n / r) ** 2 - (r - n_mod_r) * math.floor(n / r) ** 2) / 2
for _ in range(t):
	(n, m) = (int(x) for x in input().strip().split(' '))
	(left, r, right) = (1, n >> 1, n - 1)
	while left < right:
		m_r = compute_edges(n, r)
		m_r1 = compute_edges(n, r + 1)
		if m_r1 < m:
			left = r + 1
		elif m <= m_r:
			right = r - 1
		else:
			break
		r = left + right >> 1
	print(r + 1)


import math

def exact(n, k):
	return (n * n - n % k * math.ceil(n / k) ** 2 - (k - n % k) * math.floor(n / k) ** 2) / 2
for case in range(int(input())):
	(N, M) = map(int, input().split())
	k = math.ceil(N * N / (N * N - 2 * M))
	while M > exact(N, k):
		k += 1
	print(k)


import math

def exact(n, k):
	return (n * n - n % k * math.ceil(n / k) ** 2 - (k - n % k) * math.floor(n / k) ** 2) / 2
for case in range(int(input())):
	(N, M) = map(int, input().split())
	k = math.ceil(N * N / (N * N - 2 * M))
	while M > exact(N, k):
		k += 1
	print(k)


import math

def s1(n, m):
	ga = n % m
	gb = m - ga
	sa = n // m + 1
	sb = n // m
	return ga * gb * sa * sb + ga * (ga - 1) * sa * sa // 2 + gb * (gb - 1) * sb * sb // 2

def s(n, c):
	l = 1
	h = n + 1
	while l + 1 < h:
		m = l + (h - l) // 2
		k = s1(n, m)
		if k < c:
			l = m
		else:
			h = m
	return h
t = int(input())
for i in range(t):
	(n, m) = [int(j) for j in input().split()]
	print(s(n, m))


import math

def edges(n, r):
	return (n * n - n % r * math.ceil(n / r) * math.ceil(n / r) - (r - n % r) * math.floor(n / r) * math.floor(n / r)) / 2
t = int(input().strip())
for t_i in range(t):
	(n, m) = map(int, input().strip().split())
	k = 1
	y = edges(n, k)
	while y < m:
		k *= 2
		y = edges(n, k)
	lo = k / 2
	hi = k
	epsilon = y - m
	ans = None
	while True:
		mid = math.floor((lo + hi) / 2)
		k = mid
		y = edges(n, k)
		if y < m:
			lo = mid
		else:
			hi = mid
		if y - m == epsilon and y < m:
			ans = k
			break
		else:
			epsilon = y - m
	print(ans + 1)


import math

def turan(n, k):
	return (n ** 2 - n % k * math.ceil(n / k) ** 2 - (k - n % k) * (n // k) ** 2) // 2

def binary(n, m, start, end):
	if start == end:
		return start
	mid = (start + end) // 2
	cur = turan(n, mid - 1) + 1
	if cur == m:
		return mid
	elif cur > m:
		return binary(n, m, start, mid)
	else:
		if turan(n, mid) + 1 > m:
			return mid
		return binary(n, m, mid + 1, end)
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	print(binary(n, m, 2, n))


from math import ceil, floor

def turan(n, r):
	nmr = n % r
	ce = ceil(n / r)
	fl = floor(n / r)
	return (n * n - nmr * ce * ce - (r - nmr) * fl * fl) // 2

def left_lim(func, left_guess, right_guess):
	(l, r) = (left_guess, right_guess)
	(fl, fr) = (func(l), func(r))
	while l + 1 < r:
		m = l + (r - l) // 2
		fm = func(m)
		if fm > 0:
			(r, fr) = (m, fm)
		elif fm < 0:
			(l, fl) = (m, fm)
		else:
			return m
	return r
for _ in range(int(input())):
	(V, E) = map(int, input().strip().split())
	print(left_lim(lambda x: turan(V, x) - E, 1, V + 1))


import math

def exact(n, k):
	return (n * n - n % k * math.ceil(n / k) ** 2 - (k - n % k) * math.floor(n / k) ** 2) / 2
for case in range(int(input())):
	(N, M) = map(int, input().split())
	k = math.ceil(N * N / (N * N - 2 * M))
	while M > exact(N, k):
		k += 1
	print(k)


import sys
import math
MOD = 10 ** 9 + 7

def parseInt():
	return list(map(int, input().split()))
sys.setrecursionlimit(100000)

def turan(n, k):
	return (n ** 2 - n % k * math.ceil(n / k) ** 2 - (k - n % k) * (n // k) ** 2) // 2
t = int(input())
for _ in range(t):
	(n, m) = parseInt()
	start = 0
	end = n
	while start < end:
		mid = (end + start) // 2
		if turan(n, mid) < m:
			start = mid + 1
		else:
			end = mid
	print(end)


import math

def turan(n, k):
	return (n ** 2 - n % k * math.ceil(n / k) ** 2 - (k - n % k) * (n // k) ** 2) // 2
t = int(input().strip())
for _ in range(t):
	(n, m) = tuple(map(int, input().split()))
	left = 1
	right = n
	while left < right:
		mid = (left + right) // 2
		if turan(n, mid) >= m:
			right = mid
		else:
			left = mid + 1
	print(left)


import sys
import math

def solve(n, m):

	def turan(n, k):
		return (n ** 2 - n % k * math.ceil(n / k) ** 2 - (k - n % k) * (n // k) ** 2) // 2
	print('n=%d m=%d' % (n, m), file=sys.stderr)
	(kl, tl) = (1, 0)
	(kr, tr) = (n, turan(n, n))
	while kr - kl > 1:
		print('kl=%d kr=%d' % (kl, kr), file=sys.stderr)
		k = (kr + kl) // 2
		t = turan(n, k)
		if t < m:
			kl = k
		else:
			kr = k
	print('kl=%d kr=%d' % (kl, kr), file=sys.stderr)
	t = turan(n, kl)
	if t >= m:
		k = kl
	else:
		k = kr
	return k
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	print(solve(n, m))


import math

def f(n, k, e):
	return e > 0.5 * (n ** 2 - n % k * math.ceil(n / k) ** 2 - (k - n % k) * math.floor(n / k) ** 2)

def solve(n, m):
	(l, r) = (1, n * (n - 1) // 2)
	while l < r:
		k = l + (r - l + 1) // 2
		if f(n, k, m):
			l = k
		else:
			r = k - 1
	return l + 1
tt = int(input())
for _ in range(tt):
	(n, m) = input().split()
	(n, m) = (int(n), int(m))
	k = solve(n, m)
	print(k)


def turan(n, k):
	fl = n // k
	ce = n // k
	mo = n % k
	if n % k > 0:
		ce += 1
	return (n * n - mo * ce * ce - (k - mo) * fl * fl) // 2
for tc in range(int(input())):
	(n, m) = map(int, input().split())
	lo = 1
	hi = n
	while lo < hi:
		mid = (lo + hi) // 2
		if m <= turan(n, mid):
			hi = mid
		else:
			lo = mid + 1
	print(hi)


from sys import stdin
import math
t = int(stdin.readline())
for i in range(t):
	(n, m) = [int(k) for k in stdin.readline().split()]
	low = 1
	high = n
	while high > low:
		k = (low + high) // 2
		max_edges = (n * n - n % k * math.ceil(n / k) ** 2 - (k - n % k) * (n // k) ** 2) // 2
		if max_edges < m:
			low = k + 1
		else:
			high = k
	print(low)


a = int(input().strip())
l = []
for t in range(a):
	l.append(tuple(map(int, input().strip().split(' '))))
for tt in l:
	a = tt[0]
	b = tt[1]
	(g, f) = (a, 0)
	import math
	while True:
		c = (g + f) // 2
		if c == f:
			print(c + 1)
			break
		if a ** 2 - a % c * math.ceil(a / c) ** 2 - (c - a % c) * (a // c) ** 2 < 2 * b:
			(g, f) = (g, c)
		else:
			(g, f) = (c, f)
		c += 1


from math import ceil, floor

def least_edges_rplus1_clique(n, r):
	return (n * n - n % r * pow(ceil(n / r), 2) - (r - n % r) * pow(n // r, 2)) / 2
T = int(input())
for _ in range(T):
	(n, m) = [int(i) for i in input().split()]
	left = 0
	right = n - 1
	while left < right:
		r = ceil(left + (right - left) / 2)
		if least_edges_rplus1_clique(n, r) < m:
			left = r
		else:
			right = r - 1
	print(left + 1)


import math

def exact(n, k):
	return (n * n - n % k * math.ceil(n / k) ** 2 - (k - n % k) * math.floor(n / k) ** 2) / 2
for case in range(int(input())):
	(N, M) = map(int, input().split())
	k = math.ceil(N * N / (N * N - 2 * M))
	while M > exact(N, k):
		k += 1
	print(k)


import math
T = int(input().strip())

def turan(n, k):
	return (n ** 2 - n % k * math.ceil(n / k) ** 2 - (k - n % k) * (n // k) ** 2) // 2
for _ in range(T):
	(n, m) = input().strip().split()
	(n, m) = [int(n), int(m)]
	l = 0
	h = n
	mid = 0
	while l < h:
		mid = math.floor((l + h) / 2)
		if turan(n, mid) >= m:
			h = mid
		else:
			l = mid + 1
	print(l)


from math import ceil
for _ in range(int(input())):
	(n, m) = [int(x) for x in input().split()]
	lo = 1
	high = n
	while high > lo:
		mid = (lo + high) // 2
		e = (n * n - n % mid * int(ceil(n / mid)) ** 2 - (mid - n % mid) * (n // mid) ** 2) / 2
		if m > e:
			lo = mid + 1
		else:
			high = mid
	print(high)


import math

def exact(n, k):
	return (n * n - n % k * math.ceil(n / k) ** 2 - (k - n % k) * math.floor(n / k) ** 2) / 2
for case in range(int(input())):
	(N, M) = map(int, input().split())
	k = math.ceil(N * N / (N * N - 2 * M))
	while M > exact(N, k):
		k += 1
	print(k)


import math

def exact(n, k):
	return (n * n - n % k * math.ceil(n / k) ** 2 - (k - n % k) * math.floor(n / k) ** 2) / 2
for case in range(int(input())):
	(N, M) = map(int, input().split())
	k = math.ceil(N * N / (N * N - 2 * M))
	while M > exact(N, k):
		k += 1
	print(k)


import math

def exact(n, k):
	return (n * n - n % k * math.ceil(n / k) ** 2 - (k - n % k) * math.floor(n / k) ** 2) / 2
for case in range(int(input())):
	(N, M) = map(int, input().split())
	k = math.ceil(N * N / (N * N - 2 * M))
	while M > exact(N, k):
		k += 1
	print(k)


import sys
from math import ceil, floor
T = int(input().strip())

def ch(r, N):
	val = 0.5 * (N ** 2 - N % r * ceil(N / r) ** 2 - (r - N % r) * floor(N / r) ** 2)
	return val

def binS(M, N):
	r = N
	search = True
	lower_bound = 0
	upper_bound = N
	while search:
		if ch(r - 1, N) < M and ch(r, N) >= M:
			search = False
			break
		if ch(r, N) < M and ch(r + 1, N) >= M:
			search = False
			r = r + 1
			break
		if M < ch(r, N):
			if r < upper_bound:
				upper_bound = r
		elif r > lower_bound:
			lower_bound = r
		r = round((upper_bound + lower_bound) / 2)
	return r
for i in range(T):
	(N, M) = [int(temp) for temp in input().strip().split(' ')]
	val = binS(M, N)
	print(val)


import math

def exact(n, k):
	return (n * n - n % k * math.ceil(n / k) ** 2 - (k - n % k) * math.floor(n / k) ** 2) / 2
for case in range(int(input())):
	(N, M) = map(int, input().split())
	k = math.ceil(N * N / (N * N - 2 * M))
	while M > exact(N, k):
		k += 1
	print(k)


import math

def t(n, k):
	n2 = n * n
	nmk = n % k
	return (n2 - nmk * math.ceil(n / k) ** 2 - (k - nmk) * (n // k) ** 2) // 2
T = int(input())
for _ in range(T):
	(n, m) = map(int, input().split())
	(k_low, k_high) = (1, n * (n - 1))
	while k_low + 1 < k_high:
		k_mid = (k_low + k_high) // 2
		if t(n, k_mid) < m:
			k_low = k_mid
		else:
			k_high = k_mid
	if t(n, k_high) < m:
		print(k_high + 1)
	else:
		print(k_low + 1)


from math import ceil

def turan(n, k):
	num = n ** 2 - n % k * int(ceil(n / k)) ** 2 - (k - n % k) * int(n / k) ** 2
	return int(num / 2)
q = int(input())
for i in range(q):
	data = [int(i) for i in input().split()]
	n = data[0]
	m = data[1]
	left_k = 1
	right_k = n
	while left_k < right_k:
		center_k = (left_k + right_k) // 2
		if turan(n, center_k) >= m:
			right_k = center_k
		else:
			left_k = center_k + 1
	print(left_k)


import math

def exact(n, k):
	return (n * n - n % k * math.ceil(n / k) ** 2 - (k - n % k) * math.floor(n / k) ** 2) / 2
for case in range(int(input())):
	(N, M) = map(int, input().split())
	k = math.ceil(N * N / (N * N - 2 * M))
	while M > exact(N, k):
		k += 1
	print(k)


for _ in range(int(input().strip())):
	(N, M) = map(int, input().strip().split(' '))
	(N2, low, high, mid) = (N * N, 1, N + 1, 1 + N + 1 >> 1)
	while low != mid:
		if (N2 - N % mid * ((N + mid - 1) // mid) ** 2 - (mid - N % mid) * (N // mid) ** 2) // 2 >= M:
			high = mid
		else:
			low = mid
		mid = low + high >> 1
	print(mid + 1)


import os
import sys
import math

def clique(n, Ans):
	return (n * n - n % Ans * math.ceil(n / Ans) ** 2 - (Ans - n % Ans) * math.floor(n / Ans) ** 2) / 2
t = int(input())
for t_itr in range(t):
	nm = input().split()
	n = int(nm[0])
	m = int(nm[1])
	Ans = math.ceil(n * n / (n * n - 2 * m))
	while m > clique(n, Ans):
		Ans = Ans + 1
	print(Ans)


import math

def exact(n, k):
	return (n * n - n % k * math.ceil(n / k) ** 2 - (k - n % k) * math.floor(n / k) ** 2) / 2
for case in range(int(input())):
	(N, M) = map(int, input().split())
	k = math.ceil(N * N / (N * N - 2 * M))
	while M > exact(N, k):
		k += 1
	print(k)