Watson gives Sherlock two integers, $n$ and $\boldsymbol{\mbox{k}}$, and asks him to count the number of positive integer $\boldsymbol{i}$'s such that: 

$i\cdot(n-i)\leq n\cdot k,\ \text{and}\ i<n$  

Given $\textit{q}$ queries where each query consists of some $n$ and $\boldsymbol{\mbox{k}}$, print the number of possible $\boldsymbol{i}$'s for each query on a new line.

Input Format

The first line contains an integer, $\textit{q}$, denoting the number of times Watson queries Sherlock. 

Each of the $\textit{q}$ subsequent lines contains two space-separated integers denoting the respective values of $n$ and $\boldsymbol{\mbox{k}}$ for a query.

Constraints

$1\leq q\leq10^5$   
$1\leq n,k\leq10^9$

Output Format

For each query, print the number of $\boldsymbol{i}$'s satisfying the given formula on a new line.

Sample Input
2
5 1
5 2

Sample Output
2
4

Explanation

Sherlock performs the following $q=2$ queries:

The possible values of $\boldsymbol{i}$ satisfying Watson's formula for $n=5$ and $k=1$ are $\mbox{1}$ and $\begin{array}{c}4\end{array}$. Because there are two such values, we print $2$ on a new line.
The possible values of $\boldsymbol{i}$ satisfying Watson's formula for $n=5$ and $k=2$ are $\mbox{I}$, $2$, $3$, and $\begin{array}{c}4\end{array}$. Because there are four such values, we print $\begin{array}{c}4\end{array}$ on a new line.

Source: hackerrank | Difficulty: EASY
Tags: Geometry


Solutions:
import sys
from math import ceil
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = [int(c) for c in sys.stdin.readline().split()]
	if N * N - 4 * N * K < 0:
		print(N - 1)
	else:
		z1 = (N + (N * N - 4 * N * K) ** 0.5) / 2
		z2 = (N - (N * N - 4 * N * K) ** 0.5) / 2
		u = min(N, int(ceil(z1)))
		l = max(0, int(z2))
		print(min(N - 1, l + N - u))


import math
T = int(input())
for t in range(T):
	(N, K) = [int(e) for e in input().split()]
	lhs_max = N * N / 4 if N % 2 == 0 else int(N / 2) * (int(N / 2) + 1)
	if N * K >= lhs_max:
		print(N - 1)
	else:
		I = int((N - math.sqrt(N * N - 4 * N * K)) / 2)
		print(2 * I)


import math
t = int(input())
for i in range(t):
	[n, k] = [int(i) for i in input().split()]
	count = 0
	if n * n - 4 * n * k > 0:
		smallRoot = int(math.floor(n / 2 - math.sqrt(n * n - 4 * n * k) / 2))
		largeRoot = int(math.ceil(n / 2 + math.sqrt(n * n - 4 * n * k) / 2))
		if largeRoot <= 0:
			count = n - 1
		elif smallRoot <= 0:
			if largeRoot >= n:
				count = 0
			else:
				count = n - largeRoot
		elif n <= smallRoot:
			count = n - 1
		elif n > smallRoot and n <= largeRoot:
			count = smallRoot
		else:
			count = n - largeRoot + smallRoot
	else:
		count = n - 1
	print(count)


import math
T = int(input())
for t in range(T):
	(n, k) = str(input()).split()
	(n, k) = (int(n), int(k))
	res = 0
	if 4 * k >= n:
		res = n - 1
	else:
		res = 2 * int((n - math.sqrt(n ** 2 - 4 * n * k)) / 2)
	print(res)


def ceil(x):
	return x if int(x) == x else int(x) + 1
t = int(input())
for tt in range(t):
	data = input().rstrip().split()
	n = int(data[0])
	k = int(data[1])
	d = n * (n - 4 * k)
	ans = None
	if d <= 0:
		ans = n - 1
	else:
		sqd = d ** 0.5
		i1 = int((n - sqd) / 2)
		i2 = int(ceil((n + sqd) / 2))
		i1 = i1 if i1 > 0 else 0
		i2 = i2 if i2 < n else n
		ans = i1 + (n - i2)
	print(ans)


import math

def sol(n, k):
	d = n * n - 4 * n * k
	if d < 0:
		return n - 1
	(i1, i2) = ((n - math.sqrt(d)) / 2, (n + math.sqrt(d)) / 2)
	i1 = math.floor(i1)
	i2 = math.ceil(i2)
	if i1 == i2:
		return n - 1
	s = min(i1, n - 1) + n - min(n - 1, i2)
	return s

def brute(n, k):
	x = [i for i in range(1, n) if i * (n - i) <= n * k]
	return len(x)
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = sol(n, k)
	print(s)

def test():
	for n in range(1, 10000):
		for k in range(1, 10):
			if sol(n, k) != brute(n, k):
				print(n, k, sol(n, k), brute(n, k))


def f(i):
	return i * (N - i) <= NK
for _ in range(int(input())):
	(N, K) = map(int, input().split())
	N2 = N // 2
	NK = N * K
	if f(N2):
		print(N - 1)
	else:
		a = 1
		b = N2
		while a + 1 < b:
			m = (a + b) // 2
			if f(m):
				a = m
			else:
				b = m
		print(a * 2)


def read_ints():
	return map(int, input().strip().split())

def maketest(n, k):
	Delta = n * n - 4 * n * k
	if Delta <= 0:
		return n - 1
	else:
		sq = pow(Delta, 0.5)
		d = max(int((n - sq) // 2), 0)
		return 2 * d
(T,) = read_ints()
for t in range(T):
	(n, k) = read_ints()
	print(maketest(n, k))


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	discriminant = N * N - 4 * N * K
	if N <= 4 * K:
		print(N - 1)
	else:
		minRoot = (N - discriminant ** 0.5) / 2
		maxRoot = (N + discriminant ** 0.5) / 2
		print(int(minRoot) + int(N - maxRoot))


import math
import copy
import sys
import random
import time
the_start_time = time.time()
MODULO = 10 ** 9 + 7

def resolve(N, K):
	_delta = N * N - 4 * N * K
	_mask = 1
	if _delta <= 0:
		return N - 1
	x1 = int(math.floor(0.5 * (N + _delta ** 0.5)))
	x2 = int(math.floor(0.5 * (N - _delta ** 0.5)))
	if x1 == 0.5 * (N + _delta ** 0.5):
		_mask = 0
	return N - (x1 - x2) - _mask
T = int(input().strip())
for i in range(T):
	case = [int(k) for k in input().strip().split()]
	print(resolve(case[0], case[1]))


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	if N <= 4 * K:
		print(N - 1)
	else:
		discriminant = N * N - 4 * N * K
		minRoot = (N - discriminant ** 0.5) / 2
		maxRoot = (N + discriminant ** 0.5) / 2
		print(int(minRoot) + int(N - maxRoot))


import math
t = int(input())
for _ in range(0, t):
	(n, k) = [int(x) for x in input().split()]
	num = n ** 2 - 4 * n * k
	if num <= 0:
		print(n - 1)
	else:
		print(2 * int((n - math.ceil(math.sqrt(num))) / 2))


import math

def int_before_root(x, f, t):
	for i in range(int(x) - t, int(x) + t):
		if f(i) < 0 and f(i + 1) > 0:
			return i
		if f(i) == 0:
			return i
	raise ValueError("Didn't find root")

def int_after_root(x, f, t):
	for i in range(int(x) - t, int(x) + t):
		if f(i) > 0 and f(i + 1) < 0:
			return i + 1
		if f(i) == 0:
			return i
	raise ValueError("Didn't find root")

def solve_efficient(N, K):
	descriminant = N ** 2 - 4 * N * K
	if N - 4 * K <= 0:
		return N - 1
	else:
		lhs = (N - math.sqrt(descriminant)) / 2
		rhs = (N + math.sqrt(descriminant)) / 2
		f = lambda x: -x ** 2 + x * N - N * K
		lhs = int_before_root(lhs, f, 1)
		rhs = int_after_root(rhs, f, 1)
		before = lhs
		after = N - rhs if N > rhs else 0
		return before + after

def solve_naive(N, K):
	return len([1 for i in range(1, N) if i * (N - i) <= N * K])
N = int(input())
for i in range(N):
	(N, K) = map(int, input().split())
	print(solve_efficient(N, K))


T = int(input())
for i in range(0, T):
	n = [int(x) for x in input().split()]
	c = n[0] * n[1]
	b = n[0]
	det = b ** 2 - 4 * c
	if det <= 0:
		print(str(n[0] - 1))
		continue
	x1 = int((b - det ** 0.5) * 0.5)
	print(str(x1 * 2))


import math
for t in range(int(input())):
	(N, K) = [int(x) for x in input().split()]
	D = N * (N - 4 * K)
	if D <= 0:
		print(N - 1)
	else:
		sqrtD = math.sqrt(D)
		print(math.floor((N - sqrtD) / 2) + (N - math.ceil((N + sqrtD) / 2)))


from math import sqrt, ceil, floor
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if k >= n / 4:
		print(n - 1)
	else:
		d = sqrt(n * (n - 4 * k))
		minv = floor((n - d) / 2)
		maxv = ceil((n + d) / 2)
		print(n - maxv + minv)


from math import floor, ceil

def ints_in_range(a, b):
	return 0 if b < a else floor(b) - ceil(a - 1)
for i in range(int(input())):
	(n, k) = [int(s) for s in input().split()]
	if k >= n / 4:
		print(n - 1)
	else:
		det = (n ** 2 - 4 * k * n) ** 0.5
		print(ints_in_range(1, 0.5 * (n - det)) + ints_in_range(0.5 * (n + det), n - 1))


import math

def counting(N, K):
	if 4 * K >= N:
		return N - 1
	else:
		t = N / 2 - math.sqrt(N * N - 4 * N * K) / 2
		return int(t) * 2

def main():
	t = int(input())
	while t:
		(N, K) = [int(x) for x in input().split()]
		print(counting(N, K))
		t -= 1
main()


from math import sqrt, floor, ceil
for t in range(int(input())):
	(n, k) = map(int, input().split())
	d = n * n - 4 * n * k
	if d <= 0:
		print(n - 1)
	else:
		print(2 * int((n - sqrt(d)) / 2))


import math
for i in range(int(input())):
	(n, k) = [int(j) for j in input().split(' ')]
	if n < 4 * k:
		print(n - 1)
		continue
	root = (n - math.sqrt(n ** 2 - 4 * n * k)) // 2
	if root < 1:
		print(0)
		continue
	print(int(root * 2) - (n == 4 * k))


T = int(input())
while T > 0:
	T -= 1
	line = input().split()
	N = int(line[0])
	K = int(line[1])
	if N * N <= 4 * N * K:
		print(N - 1)
		continue
	ans = int((N - (N * N - 4 * N * K) ** 0.5) / 2) * 2
	print(str(ans))


import math
total_test_case = int(input())
for _ in range(total_test_case):
	(n, k) = [int(x) for x in input().split()]
	inner_part = n * n - 4 * n * k
	if inner_part <= 0:
		print(n - 1)
	else:
		margin_index = math.floor((n - math.sqrt(inner_part)) / 2)
		eval_value1 = margin_index * (n - margin_index) - n * k
		margin_index = margin_index + 1
		eval_value2 = margin_index * (n - margin_index) - n * k
		if eval_value1 > 0:
			print(2 * (margin_index - 2))
		elif eval_value2 > 0:
			print(2 * (margin_index - 1))


import sys
from math import floor, sqrt
source = sys.stdin
T = int(source.readline())
for _ in range(T):
	[N, K] = [int(s) for s in source.readline().split()]
	if K >= N / 4:
		print(N - 1)
	else:
		ans = 2 * floor((N - sqrt(N * (N - 4 * K))) / 2)
		print(ans)


from math import sqrt
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	d = n * (n - 4 * k)
	if d <= 0:
		s = max(0, n - 1)
	else:
		s = 2 * int(0.5 * (n - sqrt(d)))
	print(s)


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	if N <= 4 * K:
		print(N - 1)
	else:
		discriminant = N * N - 4 * N * K
		minRoot = (N - discriminant ** 0.5) / 2
		maxRoot = (N + discriminant ** 0.5) / 2
		print(int(minRoot) + int(N - maxRoot))


from math import sqrt, ceil, floor

def solveQ(n, k):
	d = n ** 2 - 4 * n * k
	if d < 0:
		return None
	d = sqrt(d)
	return [(n - d) / 2, (n + d) / 2]
t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	res = solveQ(n, k)
	if res == None or res[0] == res[1]:
		print(n - 1)
	else:
		res[0] = max(res[0], 0)
		print(floor(res[0]) + n - ceil(res[1]))


import math

def test(i, n, k):
	return i * (n - i) <= n * k

def search_between(bot, top, n, k):
	if bot == top:
		return bot
	diff = top - bot
	mid = top - diff // 2
	if test(mid, n, k):
		return search_between(mid, top, n, k)
	else:
		return search_between(bot, mid - 1, n, k)
for t in range(int(input())):
	[n, k] = list(map(int, input().split()))
	p = search_between(1, math.ceil(n / 2), n, k)
	if p == n - p + 1:
		p -= 1
	if p == n - p:
		p -= 0.5
	print(int(p * 2))


import math

def SherlockNumbers(N, K):
	determinant = N * N - 4 * N * K
	if determinant <= 0:
		return N - 1
	root1 = (-N + math.sqrt(determinant)) / -2
	root2 = (-N - math.sqrt(determinant)) / -2
	root_low = min(root1, root2)
	root_high = max(root1, root2)
	lowmax = int(math.floor(root_low))
	highmin = int(math.ceil(root_high))
	low_numbers = lowmax
	high_numbers = N - highmin
	return low_numbers + high_numbers
num_cases = int(input())
for case in range(num_cases):
	(N, K) = map(int, input().split(' '))
	outval = SherlockNumbers(N, K)
	print(outval)


T = int(input())
for case in range(T):
	line = input().split()
	N = int(line[0])
	K = int(line[1])
	NK = N * K
	hi = N >> 1
	if hi * (N - hi) <= NK:
		print(N - 1)
	else:
		hi -= 1
		lo = 1
		while lo < hi:
			mid = lo + hi + 1 >> 1
			if mid * (N - mid) <= NK:
				lo = mid
			else:
				hi = mid - 1
		print(2 * hi)


t = int(input())
for _ in range(t):
	s = list(map(int, input().split()))
	n = s[0]
	k = s[1]
	x = n * n - 4 * n * k
	if x <= 0:
		out = n - 1
	else:
		m = pow(x, 0.5)
		y = int((n - m) / 2)
		z = (n + m) / 2
		w = int(z)
		if w == z:
			out = y + n - w
		else:
			out = y + n - w - 1
	print(out)


t = int(input())
for ii in range(t):
	(n, k) = map(int, input().split())
	bar = n * k
	temp = int(n / 2)
	check = temp * (n - temp)
	if check <= bar:
		print(n - 1)
	else:
		l = 1
		h = temp - 1
		while 1:
			mid = int((l + h) / 2)
			a1 = mid * (n - mid)
			a2 = (mid + 1) * (n - mid - 1)
			if a1 > bar:
				h = mid - 1
			elif a2 < bar:
				l = mid + 1
			elif a2 == bar:
				print(2 * (mid + 1))
				break
			elif a1 == bar:
				print(2 * mid)
				break
			else:
				print(2 * mid)
				break


T = int(input())
for t in range(T):
	(N, K) = input().split()
	(N, K) = [int(N), int(K)]
	if K >= N / 4:
		print(N - 1)
	else:
		D = (N * (N - 4 * K)) ** 0.5
		a = (N - D) / 2
		if a == int(a):
			b = N - int((N + D) / 2)
		else:
			b = N - 1 - int((N + D) / 2)
		print(int(a) + b)


import math
for _ in range(int(input())):
	(N, K) = map(int, input().split())
	D = N * (N - 4 * K)
	if D <= 0:
		print(N - 1)
	else:
		print(2 * math.floor((N - math.ceil(math.sqrt(D))) / 2))


import math

def read_ints():
	return [int(x) for x in input().strip().split(' ')]

def read_int():
	return int(input().strip())

def compute(N, K):
	dv = N * N - 4 * N * K
	if dv < 0:
		return N - 1
	else:
		v1 = (N + math.sqrt(dv)) / 2
		v2 = (N - math.sqrt(dv)) / 2
		v1 = int(math.ceil(v1))
		v2 = int(v2)
		sec = max(0, v2) + N - min(N, v1)
		return min(N - 1, sec)
T = read_int()
for _ in range(T):
	(N, K) = read_ints()
	nc = compute(N, K)
	print(nc)


import math
for _ in range(int(input())):
	(N, K) = (int(x) for x in input().split())
	if K >= N / 4:
		print(N - 1)
	else:
		D = (N - math.sqrt(N ** 2 - 4 * N * K)) / 2
		d = math.floor(D)
		print(2 * d)


from math import floor
T = int(input())
for _ in range(T):
	(N, K) = map(int, input().split())
	(a, b, c) = (-1, N, -N * K)
	d = b ** 2 - 4 * a * c
	if d > 0:
		(x1, x2) = ((-b + d ** 0.5) / (2 * a), (-b - d ** 0.5) / (2 * a))
		(d1, d2) = (min(x1, x2) - 0, N - max(x1, x2))
		print(floor(d1) + floor(d2))
	else:
		print(N - 1)


from math import sqrt, ceil, floor
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	if n > 4 * k:
		delta = sqrt(n * (n - 4 * k))
		print(n - int(ceil((n + delta) / 2)) + int(floor((n - delta) / 2)))
	else:
		print(n - 1)


for _ in range(int(input().strip())):
	(n, k) = tuple([int(x) for x in input().strip().split(' ')])
	if n <= 4 * k:
		print(n - 1)
		continue
	print(int((n - (n * (n - 4 * k)) ** 0.5) / 2) * 2)


from math import sqrt
q = int(input())
for j in range(q):
	(n, k) = (int(i) for i in input().split())
	D = n ** 2 - 4 * n * k
	if D <= 0:
		print(n - 1)
	else:
		x1 = int((n - sqrt(D)) / 2)
		x2 = int(n - (n + sqrt(D)) / 2)
		print(x1 + x2)


from math import floor, sqrt
q = int(input())
cases = [[int(s) for s in input().split()] for i in range(q)]
for (n, k) in cases:
	det = n ** 2 - 4 * n * k
	if det < 0:
		print(n - 1)
	else:
		i_crit = (n - sqrt(det)) / 2
		if n % 2 == 0 and 2 * i_crit == n:
			print(n - 1)
		else:
			print(2 * floor(i_crit))


import math
numTests = int(input())
for _ in range(numTests):
	(n, k) = map(int, input().split())
	D = n ** 2 - 4 * n * k
	if D <= 0:
		print(n - 1)
	else:
		i1 = (n - math.sqrt(D)) / 2
		i2 = (n + math.sqrt(D)) / 2
		print(math.floor(i1) + n - math.ceil(i2))


def f(i):
	return i * (n - i) - k * n
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	lo = 1
	assert f(lo) <= 0
	hi = n // 2
	if f(hi) <= 0:
		print(n - 1)
	else:
		while lo + 1 < hi:
			m = (lo + hi) // 2
			if f(m) <= 0:
				lo = m
			else:
				hi = m
		print(2 * lo)


import math
q = int(input())
while q > 0:
	q -= 1
	(n, k) = list(map(int, input().split()))
	count = 0
	if k >= n / 4:
		print(n - 1)
	else:
		r = n * (n / 4 - k)
		imax = int(n / 2 - math.sqrt(r))
		print(2 * imax)


q = int(input().strip())
for i in range(q):
	(n, k) = [int(valore) for valore in input().strip().split(' ')]
	c = n ** 2 / 4 - n * k
	rad_max = n / 2 + c ** 0.5
	risultato = n - 1 if c <= 0 else int(n / 2 - c ** 0.5) + n - int(n / 2 + c ** 0.5) - 1
	if c > 0 and rad_max.is_integer():
		risultato += 1
	print(risultato)


import sys
n = int(input().strip())
for a0 in range(n):
	(n, k) = input().strip().split(' ')
	(n, k) = [int(n), int(k)]
	if n <= 4 * k:
		print(n - 1)
	else:
		a1 = (-n + (n ** 2 - 4 * n * k) ** (1 / 2)) / -2
		a2 = (-n - (n ** 2 - 4 * n * k) ** (1 / 2)) / -2
		a = min(a1, a2)
		a = int(a) + 1
		print((a - 1) * 2)


import math
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	if n <= 4 * k:
		print(n - 1)
	else:
		dscr = math.sqrt(n * n - 4 * k * n)
		low = math.floor((n - dscr) / 2)
		high = math.ceil((n + dscr) / 2)
		print(max(0, low) + max(0, n - high))


for _ in range(int(input())):
	(n, k) = [int(a) for a in input().split()]
	if n <= 4 * k:
		print(n - 1)
	else:
		r = (n - (n * (n - 4 * k)) ** 0.5) / 2
		print(2 * int(r))


import math
q = int(input())
for _ in range(q):
	[n, k] = [int(x) for x in input().strip().split(' ')]
	if n * n - 4 * n * k <= 0:
		print(n - 1)
	else:
		r = int((n - math.sqrt(n * n - 4 * n * k)) / 2)
		print(r * 2)


import math
query = int(input())
for q in range(query):
	(n, k) = input().strip().split()
	(n, k) = [int(n), int(k)]
	coeff = n * (n - 4 * k)
	if coeff <= 0:
		print(n - 1)
	else:
		print(int(math.floor((n - math.sqrt(coeff)) / 2) + n - math.ceil((n + math.sqrt(coeff)) / 2)))


T = int(input())
for t in range(T):
	(n, k) = [int(c) for c in input().split(' ')]
	a = n * k
	d = n * n - 4 * a
	if d <= 0:
		print(n - 1)
		continue
	l = 0.5 * (n - d ** 0.5)
	l = int(l)
	r = 0.5 * (n + d ** 0.5)
	q = int(r)
	r = q if r == q else q + 1
	print(l + n - r)


import math
q = int(input())
for _ in range(q):
	(n, k) = map(int, input().split())
	if n == 1:
		print(0)
		continue
	nk = n * k
	i = n // 2
	if i * (n - i) <= nk:
		print(n - 1)
		continue
	i_toobig = i
	i_toosmall = 1
	while True:
		i = (i_toobig + i_toosmall) // 2
		if i * (n - i) <= nk:
			if i == i_toobig - 1:
				print(2 * i)
				break
			else:
				i_toosmall = i
		elif i == i_toosmall + 1:
			print(2 * i_toosmall)
			break
		else:
			i_toobig = i


import math
q = int(input())
for _ in range(q):
	x = list(map(int, input().split()))
	n = x[0]
	k = x[1]
	count = 0
	dis = n ** 2 - 4 * n * k
	if dis <= 0:
		count = n - 1
	else:
		small = (n - math.sqrt(n ** 2 - 4 * n * k)) / 2
		large = (n + math.sqrt(n ** 2 - 4 * n * k)) / 2
		count = int(small) + int(n - large)
	print(count)


import math
a = 1
for _ in range(int(input())):
	(n, k) = map(int, input().strip().split(' '))
	b = -n
	c = k * n
	d = b ** 2 - 4 * a * c
	if d > 0:
		sol2 = math.ceil((-b + math.sqrt(d)) / (2 * a))
		sol1 = math.floor((-b - math.sqrt(d)) / (2 * a))
		print(sol1 + n - sol2)
	else:
		print(n - 1)


import math
q = int(input())
for i in range(q):
	(n, k) = map(int, input().split())
	if n <= 4 * k:
		count = n - 1
	else:
		val = n * (n - 4 * k)
		sqr = math.sqrt(val)
		x1 = math.floor((n - sqr) / 2)
		x2 = math.ceil((n + sqr) / 2)
		count = n - x2 + x1
	print(count)


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	if N <= 4 * K:
		print(N - 1)
	else:
		discriminant = N * N - 4 * N * K
		minRoot = (N - discriminant ** 0.5) / 2
		maxRoot = (N + discriminant ** 0.5) / 2
		print(int(minRoot) + int(N - maxRoot))


import math
q = int(input())
for i in range(0, q):
	sl = input().split()
	n = int(sl[0])
	k = int(sl[1])
	if k < n / 4:
		print(2 * int((n - math.sqrt(n * n - 4 * n * k)) / 2))
	else:
		print(n - 1)


from math import sqrt, ceil, floor

def solve_quadratic(a, b, c):
	det = b * b - 4 * a * c
	if det < 0:
		return None
	det = sqrt(det)
	return ((-b + det) / (2 * a), (-b - det) / (2 * a))
q = int(input())
for _ in range(q):
	(n, k) = [int(x) for x in input().split()]
	count = 0
	zeroes = solve_quadratic(-1, n, -n * k)
	if zeroes:
		(x1, x2) = sorted(zeroes)
		count += max(0, floor(x1))
		count += n - min(n, ceil(x2))
		if x1 == x2:
			count -= 1
	else:
		count = n - 1
	print(count)


from math import sqrt, ceil, floor
T = int(input().strip())
for t in range(T):
	(N, K) = tuple(map(int, input().split(' ')))
	D = N ** 2 - 4 * N * K
	if D > 0:
		i1 = ceil((N + sqrt(D)) / 2)
		i2 = floor((N - sqrt(D)) / 2)
		print(i2 + N - i1)
	else:
		print(N - 1)


from math import ceil, floor, sqrt
q = int(input())
for cntQ in range(q):
	(n, k) = [int(x) for x in input().split()]
	if n <= 4 * k:
		print(n - 1)
	else:
		a = floor((n - sqrt(n * n - 4 * n * k)) / 2) + n - ceil((n + sqrt(n * n - 4 * n * k)) / 2)
		print(a)


from math import sqrt

def do_work():
	(n, k) = [int(i) for i in input().split()]
	a = 1
	b = -n
	c = n * k
	d = b ** 2 - 4 * a * c
	try:
		sol1 = (-b - sqrt(d)) / (2 * a)
	except:
		sol1 = 0
	try:
		sol2 = (-b + sqrt(d)) / (2 * a)
	except:
		sol2 = 0
	upper = int(n - sol2) if sol2 else n - 1
	lower = int(sol1) if sol1 else 0
	r = lower + upper
	if r >= n:
		r = n - 1
	print(r)
T = int(input())
for _ in range(T):
	do_work()


import math

def sol(n, k):
	if n <= 4 * k:
		return int(n - 1)
	return 2 * int((n - math.sqrt(n * (n - 4 * k))) // 2)
q = int(input())
while q > 0:
	q -= 1
	(n, k) = map(float, input().split())
	print(sol(n, k))


import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	n2 = n / 2
	if n2 ** 2 < n * k:
		ans = n - 1
	else:
		diff = n2 ** 2 - n * k
		ans = min(int(n2 - math.sqrt(diff)) * 2, n - 1)
	print(int(ans))


import math
for q in range(int(input())):
	(n, k) = map(int, input().split())
	D = n * n - 4 * n * k
	if D <= 0:
		print(n - 1)
	else:
		d = pow(D, 0.5)
		i1 = (n - d) / 2
		i2 = (n + d) / 2
		ans = max(0, int(i1)) + max(0, int(n - i2))
		print(ans)


q = int(input())
for iq in range(q):
	(n, k) = [int(x) for x in input().split()]
	max_val = n * k
	if n * k >= n // 2 * (n - n // 2):
		print(n - 1)
		continue
	head = 1
	tail = n // 2 + 1
	while tail - head > 1:
		mid = (tail + head) // 2
		if (n - mid) * mid <= max_val:
			head = mid
		else:
			tail = mid
	print(2 * head)


import math
T = int(input())
for idx in range(T):
	(n, k) = map(int, input().split())
	fn = lambda i: i * (n - i)
	D = n * (n - 4 * k)
	if D <= 0:
		s = n - 1
	else:
		d = math.sqrt(D)
		lb = int((n - d) / 2) - 1
		while fn(lb + 1) <= n * k:
			lb += 1
		s = 2 * lb
	print(s)


import math
n = int(input())
arr = []
for a0 in range(n):
	arr.append(list(map(int, input().strip().split(' '))))
for (n, k) in arr:
	delta = n ** 2 - 4 * n * k
	if delta <= 0:
		sol = n - 1
	else:
		sqrt_delta = math.sqrt(delta)
		sol1 = math.floor(max(0, n - (n + sqrt_delta) / 2.0))
		sol2 = math.floor(max(0, (n - sqrt_delta) / 2.0))
		sol = sol1 + sol2
	print(sol)


import sys
import math

def read_one():
	return int(input().strip())

def read_two():
	(x, y) = input().strip().split(' ')
	return [int(x), int(y)]

def f(n, k, i):
	return i * i - n * i + n * k

def df(n, k, i):
	return 2 * i - n

def zero(n, k):
	l = 0
	r = n
	while r - l > 1:
		x = (l + r) // 2
		value = f(n, k, x)
		if value < 0:
			r = x
		elif value > 0:
			l = x
		elif value == 0:
			return x
	if f(n, k, l) < 0:
		l = l - 1
	return l

def compute(n, k):
	minimum = f(n, k, n / 2)
	if minimum >= 0:
		return n - 1
	x = zero(n, k)
	return 2 * x
q = read_one()
assert 1 <= q <= 100000.0
for _ in range(q):
	(n, k) = read_two()
	assert 1 <= n <= 1000000000.0
	assert 1 <= k <= 1000000000.0
	x = compute(n, k)
	print(x)


def isqrt(n):
	x = n
	y = (x + 1) // 2
	while y < x:
		x = y
		y = (x + n // x) // 2
	return x

def count(n, k):
	if n <= 4 * k:
		return n - 1
	s = isqrt(n ** 2 - 4 * n * k)
	if s * s == n ** 2 - 4 * n * k:
		return n - s
	return 2 * ((n - s - 1) // 2)
q = int(input())
for i in range(q):
	(n, k) = map(int, input().split())
	print(count(n, k))


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

def solve(n, k):
	if n < 1:
		return 0
	det = math.pow(n, 2) - 4 * n * k
	if det <= 0:
		return n - 1
	else:
		lower = math.floor((n - math.sqrt(det)) / 2)
		upper = math.ceil((n + math.sqrt(det)) / 2)
		if n < lower:
			return n - 1
		elif n < upper:
			return lower
		else:
			return lower + n - upper
for _ in range(q):
	[n, k] = list(map(int, input().strip().split(' ')))
	print(solve(n, k))


import math

def count(n, k):
	if n < 4 * k:
		return n - 1
	disc = n * (n - 4 * k)
	if disc == 0:
		return n - 1
	root = math.sqrt(disc)
	x1 = (n - root) / 2
	x2 = (n + root) / 2
	result = n - int(math.ceil(x2))
	result += int(math.floor(x1))
	return result
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	result = count(n, k)
	print(result)


import sys
T = int(sys.stdin.readline())
for _ in range(T):
	(N, K) = list(map(int, sys.stdin.readline().split()))
	if N <= 4 * K:
		print(N - 1)
	else:
		discriminant = N * N - 4 * N * K
		minRoot = (N - discriminant ** 0.5) / 2
		maxRoot = (N + discriminant ** 0.5) / 2
		print(int(minRoot) + int(N - maxRoot))


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	s = max(0, n * n - 4 * n * k)
	d = (n - s ** 0.5) / 2.0
	if int(d) * 2 == n:
		print(n - 1)
	else:
		print(int(d) * 2)


import sys
from math import ceil, floor

def solve(n, k):
	print('n=%d k=%d' % (n, k), file=sys.stderr)
	print('i^2-%di+%d>=0' % (n, n * k), file=sys.stderr)
	D = n * n - 4 * n * k
	print('D=%d' % D, file=sys.stderr)
	if D < 0:
		return n - 1
	(i1, i2) = ((n - pow(D, 0.5)) / 2, (n + pow(D, 0.5)) / 2)
	print('i1=%f i2=%f' % (i1, i2), file=sys.stderr)
	(i1, i2) = (floor(i1), ceil(i2))
	print('i1=%d i2=%d' % (i1, i2), file=sys.stderr)
	if i1 == i2:
		return n - 1
	if i2 <= 1:
		return n - 1
	if i1 <= 0 and i2 < n:
		return n - i2
	if i1 <= 0 and i2 >= n:
		return n - 1
	if i1 > 0 and i2 < n:
		return i1 + n - i2
	if i1 > 0 and i2 >= n:
		return n - i1
	return n - 1
q = int(input())
for _ in range(q):
	(n, k) = map(int, input().split())
	print(solve(n, k))


from math import sqrt
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	delta = n * n - 4 * n * k
	if delta <= 0:
		print(n - 1)
	else:
		r1 = (-n - sqrt(delta)) / -2
		r2 = (-n + sqrt(delta)) / -2
		(r1, r2) = (min(r1, r2), max(r1, r2))
		r1 = int(r1)
		if r2.is_integer():
			r2 = int(r2)
		else:
			r2 = int(r2) + 1
		left = max(r1, 0)
		right = max(n - r2, 0)
		print(left + right)


from math import ceil, floor
t = int(input())
for i in range(0, t):
	(n, k) = input().strip().split()
	n = int(n)
	k = int(k)
	d = n * n - 4 * n * k
	if d <= 0:
		print(n - 1)
	else:
		root1 = (n + pow(d, 1 / 2)) / 2
		root2 = (n - pow(d, 1 / 2)) / 2
		r1 = ceil(root1)
		r2 = floor(root2)
		print(max(r2, 0) + n - max(r1, 1))


q = int(input())
for _ in range(q):
	(n, k) = [int(s) for s in input().split()]
	if n ** 2 - 4 * n * k < 0:
		print(n - 1)
	elif n ** 2 - 4 * n * k == 0:
		print(2 * int((n - (n ** 2 - 4 * n * k) ** 0.5) / 2) - 1)
	else:
		print(2 * int((n - (n ** 2 - 4 * n * k) ** 0.5) / 2))


from math import sqrt
q = int(input().strip())
for i in range(q):
	(n, k) = [int(j) for j in input().split()]
	if k >= n / 4:
		print(n - 1)
	else:
		print(int((n - sqrt(n ** 2 - 4 * n * k)) // 2 * 2))


import math
for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split(' ')]
	count = 0
	if n ** 2 - 4 * n * k <= 0:
		count = n - 1
	else:
		lower = math.floor((n - math.sqrt(n ** 2 - 4 * n * k)) / 2)
		higher = math.ceil((n + math.sqrt(n ** 2 - 4 * n * k)) / 2)
		if lower > 0 and lower < n:
			count = count + lower
		if higher > 0 and higher < n:
			count = count + n - higher
	print(count)


from math import *
for a0 in range(int(input())):
	(n, k) = list(map(int, input().split(' ')))
	disc = n ** 2 - 4 * n * k
	if disc <= 0:
		print(n - 1)
	else:
		disc = disc ** 0.5
		z1 = (n - disc) / 2
		z2 = (n + disc) / 2
		print(floor(z1) + n - ceil(z2))


from math import floor, ceil

def calc(n, k):
	d = n * (n - 4 * k)
	if d <= 0:
		return n - 1
	else:
		i1 = floor((n - d ** 0.5) / 2)
		i2 = ceil((n + d ** 0.5) / 2)
		return i1 + n - i2
q = int(input())
for i in range(q):
	[n, k] = input().split()
	[n, k] = [int(n), int(k)]
	print(calc(n, k))


def foo(n, k):
	lo = 1
	hi = n // 2
	t = n * k
	if lo * (n - lo) > t:
		return 0
	if hi * (n - hi) <= t:
		return n - 1
	while hi - lo > 1:
		mid = (hi + lo) // 2
		x = mid * (n - mid)
		if x <= t:
			lo = mid
		else:
			hi = mid
	return 2 * lo
num_q = int(input())
for _ in range(num_q):
	(n, k) = (int(x) for x in input().split())
	print(foo(n, k))


from math import ceil, sqrt, floor

def disc(a, b, c):
	return b ** 2 - 4 * a * c
for i in range(int(input())):
	(n, k) = [int(x) for x in input().split()]
	if disc(-1, n, -n * k) < 0:
		print(n - 1)
	elif disc(-1, n, -n * k) == 0:
		print(min(floor(n / 2 - sqrt(disc(-1, n, -n * k)) / 2), n) + max(0, n - ceil(n / 2 + sqrt(disc(-1, n, -n * k)) / 2)) - 1)
	else:
		print(min(floor(n / 2 - sqrt(disc(-1, n, -n * k)) / 2), n) + max(0, n - ceil(n / 2 + sqrt(disc(-1, n, -n * k)) / 2)))


from math import sqrt, floor, ceil
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	D = n * n - 4 * k * n
	if D <= 0:
		print(n - 1)
	else:
		r1 = (n - sqrt(D)) / 2
		r2 = (n + sqrt(D)) / 2
		print(floor(r1) + (n - ceil(r2)))


def solve(n, k):
	(low, high) = (1, n - 1)
	cur = (low + high) // 2
	while low < high - 1:
		x = cur * (n - cur)
		if x < n * k:
			(low, cur) = (cur, (cur + high) // 2)
		if x > n * k:
			(high, cur) = (cur, (cur + low) // 2)
		if x == n * k:
			break
	return 2 * cur - max(0, cur - (n - cur - 1))
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	print(solve(n, k))