Luis has a sequence of $n+1$ integers $a_1, a_2, \ldots, a_{n+1}$. For each $i = 1, 2, \ldots, n+1$ it is guaranteed that $0\leq a_i < n$, or $a_i=n^2$. He has calculated the sum of all the elements of the sequence, and called this value $s$.

Luis has lost his sequence, but he remembers the values of $n$ and $s$. Can you find the number of elements in the sequence that are equal to $n^2$?

We can show that the answer is unique under the given constraints.


-----Input-----

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 2\cdot 10^4$). Description of the test cases follows.

The only line of each test case contains two integers $n$ and $s$ ($1\le n< 10^6$, $0\le s \le 10^{18}$). It is guaranteed that the value of $s$ is a valid sum for some sequence satisfying the above constraints.


-----Output-----

For each test case, print one integer — the number of elements in the sequence which are equal to $n^2$.


-----Examples-----

Input
4
7 0
1 1
2 12
3 12
Output
0
1
3
1


-----Note-----

In the first test case, we have $s=0$ so all numbers are equal to $0$ and there isn't any number equal to $49$.

In the second test case, we have $s=1$. There are two possible sequences: $[0, 1]$ or $[1, 0]$. In both cases, the number $1$ appears just once.

In the third test case, we have $s=12$, which is the maximum possible value of $s$ for this case. Thus, the number $4$ appears $3$ times in the sequence.

Source: codeforces | Difficulty: EASY
Tags: Mathematics


Solutions:
from sys import stdin

def solve():
	for _ in range(int(stdin.readline().strip())):
		(n, s) = map(int, stdin.readline().rstrip().split())
		print(s // (n * n))
solve()


import sys
import math
input = sys.stdin.readline
for _ in range(int(input())):
	(n, s) = input().split()
	n = int(n)
	s = int(s)
	print(math.floor(s / (n * n)))


for s in [*open(0)][1:]:
	(n, s) = map(int, s.split())
	print(s // n // n)


import sys

def main():
	t = int(sys.stdin.readline())
	for _ in range(t):
		(n, s) = map(int, sys.stdin.readline().split())
		print(s // n ** 2)
main()


import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
for _ in range(int(input())):
	(n, s) = map(int, input().split())
	if n * n > s:
		print(0)
		continue
	ans = s // (n * n)
	print(ans)


import sys
test_cases = sys.stdin.readline()
for line in sys.stdin:
	if not line.strip():
		continue
	(n, s) = map(int, line.strip().split())
	print(s // n ** 2)


def solve(n, s):
	rem = s // n ** 2
	return rem
from sys import stdin
input = stdin.readline
t = int(input())
for i in range(t):
	(n, s) = [int(x) for x in input().split()]
	print(solve(n, s))


from math import *
from sys import *
from bisect import bisect_left as bl
from bisect import bisect_right as br
from collections import Counter as ctr
from collections import deque as dq
from array import array
input = stdin.readline
inp = lambda : int(input())
li = lambda : list(map(int, input().split()))
lb = lambda : list(map(int, input()))
ls = lambda : list(input())
bi = lambda n: bin(n).replace('0b', '')
yn = lambda f: print('NYOE S'[f::2])
srp = lambda s, i, c: s[:i] + c + s[i + 1:]

def solve(__=1):
	for _ in range(__):
		(n, s) = li()
		print(s // n ** 2)
solve(inp())


from sys import stdin
for _ in range(int(stdin.readline())):
	arr = stdin.readline().split()
	n = int(arr[0])
	s = int(arr[1])
	print(s // n ** 2)


from sys import stdin
from math import floor

def A():
	T = int(stdin.readline())
	for _ in range(T):
		(n, s) = map(int, stdin.readline().split())
		print(s // int(n ** 2))
A()


import sys
input = sys.stdin.readline

def find_possible():
	number_examples = int(input())
	for test_case in range(number_examples):
		test_case = list(map(int, input().split()))
		n = test_case[0]
		s = test_case[1]
		if s:
			print(s // n ** 2)
		else:
			print(0)
find_possible()


import sys
import bisect
inp = sys.stdin.readline

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

def lcm(a, b):
	return a * b // gcd(a, b)
for _ in range(int(inp())):
	(n, s) = map(int, inp().split())
	print(s // n ** 2)


def solve():
	(n, s) = [int(i) for i in input().split()]
	return s // n // n
t = int(input())
ans = []
while t:
	ans.append(str(solve()))
	t -= 1
print('\n'.join(ans))


import sys

def input():
	return sys.stdin.readline().rstrip()

def main():
	t = int(input())
	for tc in range(t):
		(n, s) = map(int, input().split())
		print(s // n ** 2)
main()


import math
from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	(n, s) = map(int, input().split())
	print(s // (n * n))


t = int(input())
l = []
for i in range(t):
	(a, b) = input().split()
	n = int(a)
	s = int(b)
	c = n * n
	d = s // c
	l.append(d)
for i in l:
	print(i)


t = int(input())
s = 0
numbers = []
for i in range(t):
	(n, s) = input().split()
	n = int(n)
	s = int(s)
	n2 = n * n
	numbers.append(s // n2)
for i in numbers:
	print(i)


cases = int(input())
arr = []
for i in range(cases):
	(n, s) = input().split()
	n = int(n)
	s = int(s)
	arr.append(s // (n * n))
for i in arr:
	print(i)


from math import ceil
from sys import stdin
input = stdin.readline

def main():
	for _ in range(int(input())):
		(n, s) = map(int, input().split())
		mes = (n - 1) * (n + 1)
		if s > mes:
			init = (n - 1) * n + n ** 2
			x = init - mes
			print(ceil((s - mes) / x))
		else:
			print(0)
main()


from sys import stdin, stdout
from collections import defaultdict
input = stdin.readline
t = int(input().strip())
for _ in range(t):
	(n, s) = list(map(int, input().strip().split()))
	nsq = n * n
	cnt = 0
	cnt = s // nsq
	print(cnt)


import sys
from bisect import bisect_left as lb
from bisect import bisect_right as rb
from collections import deque
from queue import PriorityQueue as pq
from math import gcd
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
lii = lambda : list(map(int, list(ip())))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
inv = lambda x: pow(x, mod - 2, mod)
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
mod = 10 ** 9 + 7
mod1 = 998244353
for _ in range(ii()):
	(n, s) = il()
	ans = s // (n * n)
	print(ans)


out = []
for _ in range(int(input())):
	(n, s) = map(int, input().split())
	out.append(s // n ** 2)
for i in out:
	print(i)


import sys
input = sys.stdin.readline

def solve(n, s):
	print(s // n ** 2)
for _ in range(int(input())):
	(n, s) = map(int, input().split())
	solve(n, s)


from collections import deque
from re import X
import sys
for _ in range(int(sys.stdin.readline())):
	(n, s) = map(int, sys.stdin.readline().split())
	print(s // (n * n))


from enum import Enum, auto
import copy
import sys
import re
import math
import bisect
from collections import deque
input = sys.stdin.readline
INF = 987654321

def main():
	t = int(input())
	for _ in range(t):
		(n, s) = map(int, input().split())
		ret = int(s / (n * n))
		print(ret)
main()


t = int(input())
arr = []
for i in range(0, t):
	(n, k) = map(int, input().split())
	arr.append(k // (n * n))
for x in arr:
	print(x)


t = int(input())
result = []
for case in range(t):
	(n, s) = map(int, input().split())
	result.append(s // n ** 2)
for x in result:
	print(x)


import sys
input = sys.stdin.readline
print = sys.stdout.write

def main():
	t = int(input())
	for _ in range(t):
		(a, b) = map(int, input().split())
		print(f'{b // a ** 2}\n')
main()


c = int(input())
n = [0] * c
s = [0] * c
for i in range(c):
	(n[i], s[i]) = map(int, input().split())
for h in range(c):
	print(s[h] // (n[h] * n[h]))


import sys
input = sys.stdin.readline

def inp():
	return int(input())

def inlt():
	return list(map(int, input().split()))

def insr():
	s = input()
	return list(s[:len(s) - 1])

def invr():
	return map(int, input().split())
x = int(input())
for i in range(x):
	input_numbers = inlt()
	num_sqrd = input_numbers[0] * input_numbers[0]
	print(int(input_numbers[1] / num_sqrd))


t = int(input())
li = []
for i in range(t):
	(n, s) = map(int, input().split()[:2])
	j = s // n ** 2
	li.append(j)
for i in li:
	print(i)


cases = int(input())
list = []
while cases != 0:
	(n, s) = map(int, input().split())
	if s == 0:
		list.append(0)
	else:
		list.append(s // n ** 2)
	cases = cases - 1
for x in list:
	print(x)


def main():
	t = int(input())
	solutions = []
	for test in range(t):
		datas = input().split()
		n = int(datas[0])
		s = int(datas[1])
		if s < n * n:
			solutions.append(0)
		elif s == n * n:
			solutions.append(1)
		else:
			solutions.append(int(s / (n * n)))
	for ss in solutions:
		print(ss)
main()


m = []
for _ in range(int(input())):
	(n, s) = map(int, input().split())
	k = n ** 2
	m.append(s // k)
for mo in m:
	print(mo)


def count(n, s):
	return s // n ** 2
t = int(input())
lst = []
for i in range(t):
	(n, s) = map(int, input().split())
	lst.append(count(n, s))
print(*lst, sep='\n')


import sys

class Solution:

	def square_counting(self, N, S):
		return S // N ** 2
T = int(sys.stdin.readline().strip())
for t_ in range(T):
	(N, S) = [int(x_) for x_ in sys.stdin.readline().strip().split(' ')]
	s = Solution()
	print(s.square_counting(N, S))


import math
import sys
import itertools
import fractions
wtf = sys.stdin.read()
wtf = wtf.strip().split('\n')
for t in wtf[1:]:
	(n, s) = map(int, t.split())
	print(int(s // n ** 2))


from math import *
import sys
cin = lambda : sys.stdin.readline().strip()
cout = sys.stdout.write

def print_test_cases(tt, ans):
	cout(f'Case #{tt}: {ans}\n')

def read_line():
	return list(map(int, cin().split()))

def solve(tt):
	(n, s) = read_line()
	ans = s // (n * n)
	cout(str(ans))
	cout('\n')

def main():
	T = int(cin())
	for tt in range(1, T + 1):
		solve(tt)
main()


a = int(input())
b = []
for i in range(a):
	b.append(list(map(int, input().split())))
for l in b:
	print(l[1] // l[0] ** 2)


def fun(l):
	n = l[0]
	s = l[1]
	return s // (n * n)
final = []
for i in range(int(input())):
	l = list(map(int, input().split()))
	final.append(fun(l))
for i in final:
	print(i)


t = int(input())
lst = []
for i in range(t):
	(n, s) = map(int, input().split(' '))
	lst.append(s // n ** 2)
for i in lst:
	print(i)


import sys

def solve():
	inp = sys.stdin.readline
	(n, s) = map(int, inp().split())
	print(s // n ** 2)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


from math import floor
t = int(input())
result = []
for i1 in range(t):
	in1 = input().split()
	result.append(floor(int(in1[1]) / int(in1[0]) ** 2))
for i2 in result:
	print(i2)


import sys
inp = sys.stdin.readline
for _ in range(int(inp())):
	(n, s) = map(int, inp().split())
	if s < n ** 2:
		print(0)
	elif s == n ** 2:
		print(1)
	else:
		print(s // n ** 2)


results = []
for t in range(int(input())):
	(n, s) = [int(x) for x in input().split()]
	results.append(int(s / (n * n)))
print(*results, sep='\n')


t = int(input())
res = []
for i in range(t):
	ar = list(map(int, input().split()))
	n = ar[0]
	s = ar[1]
	res.append(int(s / n ** 2))
for el in res:
	print(el)


ans = ''
num = int(input())
for i in range(num):
	(n, s) = map(int, input().split())
	ans += f'{int(s / n ** 2)}\n'
print(ans)


def squre(t):
	f_lst = []
	for i in range(t):
		(a, b) = list(map(int, input().split()))
		s = b // a ** 2
		f_lst.append(s)
	return f_lst
t = int(input())
x = squre(t)
for i in x:
	print(i)


l1 = []
l2 = []
l3 = []
t = int(input())
for i in range(t):
	l1 = input().split()
	l2 = list(map(int, l1))
	l3.append(l2)
for i in range(len(l3)):
	c = l3[i][0]
	s = l3[i][1]
	print(int(s / (c * c)))


ls = []
for i in range(int(input())):
	cnt = 0
	(n, s) = input().split()
	if int(s) == 0:
		ls.append(0)
	else:
		flag = int(s) >= int(n) ** 2
		remaining = s
		if flag:
			cnt = int(s) // int(n) ** 2
			ls.append(cnt)
		else:
			ls.append(0)
for items in ls:
	print(items)


t = int(input(''))
ans = []
for i in range(t):
	(n, s) = map(int, input().split())
	if n ** 2 > s:
		ans.append(0)
	elif n == 1 and s == 1:
		ans.append(1)
	else:
		ans.append(s // n ** 2)
for i in range(t):
	print(ans[i])


import fileinput
file = fileinput.input()

def square(n, s):
	a = n ** 2
	b = int(s / a)
	print(b)
while True:
	test = []
	line = file.readline().strip()
	if line == '':
		break
	for _ in range(int(line)):
		case = file.readline().strip()
		case = case.split(' ')
		square(int(case[0]), int(case[1]))


t = int(input())
A = []
for i in range(t):
	ti = input().split(' ')
	(n, s) = (int(ti[0]), int(ti[1]))
	if s == 0:
		A.append(0)
	else:
		A.append(s // n ** 2)
for a in A:
	print(a)


alpha = []
beta = []
gamma = []
t = int(input())
for i in range(t):
	a = [int(s) for s in input().split(' ')]
	beta.append(a)
for i in range(t):
	(n, s) = beta[i]
	if n != 0:
		print(int(s / pow(n, 2)))
	else:
		print(0)


n = int(input())
arr = []
for i in range(n):
	y = [int(x) for x in input().split()]
	arr.append(y)
for i in range(len(arr)):
	print(arr[i][1] // arr[i][0] ** 2)


import math as m
t = int(input())
List = []
for k in range(0, t):
	listns = []
	inpuut = input()
	inputspl = inpuut.split()
	n = int(inputspl[0])
	s = int(inputspl[1])
	listns.append(n)
	listns.append(s)
	List.append(listns)
for element in List:
	d = element[0] ** 2
	c = m.floor(element[1] / d)
	print(c)


import math
t = int(input())
ans = []
for x in range(t):
	inp = list(map(int, input().split()))
	n = inp[0]
	s = inp[1]
	answer = math.ceil((s - n * n + 1) / (n * n - n + 1))
	if answer < 0:
		answer = 0
	ans.append(answer)
for a in ans:
	print(a)


__ = int(input())
l = []
for _ in range(__):
	a = input().split()
	l.extend(a)
w = 0
for j in range(__):
	n = int(l[w])
	s = int(l[w + 1])
	square = n ** 2
	max_value = square * (n + 1)
	y = s // square
	h = False
	if s == 0:
		pass
	elif s == max_value:
		k = s // (n + 1)
		h = True
	else:
		h = False
	w += 2
	if h:
		print(n + 1)
	else:
		print(y)


l0 = int(input())
l2 = {}
l4 = []
for i in range(l0):
	l1 = input()
	l4.append(l1.split(' '))
for i in range(l0):
	if int(l4[i][1]) != 0:
		print(int(int(l4[i][1]) / int(l4[i][0]) ** 2))
	else:
		print(0)


import math
from itertools import permutations
from re import X
n = int(input(''))
LIST = []
for i in range(n):
	line = list(map(int, input().split()))
	LIST.append(line)
for numbers in LIST:
	n = numbers[0]
	s = numbers[1]
	print(math.floor(s / n ** 2))


def function(testCases):
	while testCases != 0:
		(n, s) = input().split(' ')
		n = int(n)
		s = int(s)
		print(s // (n * n))
		testCases -= 1
function(int(input()))


for _ in range(int(input())):
	(n, s) = map(int, input().split())
	if s == 0:
		print(0)
	else:
		n2 = n * n
		ans = s // n2
		print(ans)


for _ in range(int(input())):
	(n, s) = map(int, input().split())
	print(s // (n * n))


import math
try:
	for _ in range(int(input())):
		(n, k) = map(int, input().split())
		n = n
		ans = k // (n * n)
		if k == 0:
			print(0)
			continue
		print(ans)
except:
	pass


x = int(input())
for i in range(x):
	(n, s) = map(int, input().split())
	print(s // (n * n))


n = int(input())
for i in range(n):
	m = input().split()
	a = int(m[0])
	b = int(m[1])
	s = a ** 2
	if b == 0:
		print('0')
	else:
		print(b // s)


t = int(input())
while t:
	t -= 1
	(n, s) = map(int, input().split())
	x = n * n
	if s >= x:
		print(s // x)
	else:
		print(0)


for i in range(int(input())):
	(A, B) = map(int, input().split())
	print(B // A ** 2)


a = int(input())
for i in range(a):
	(a, b) = map(int, input().split())
	print(b // a ** 2)


t = int(input())
for i in range(t):
	(n, s) = map(int, input().split())
	if s >= n:
		print(s // (n * n))
	else:
		print(0)


for i in range(int(input())):
	(n, s) = map(int, input().split())
	k = n * n
	print(s // k)