Square Counting

题意翻译

有一个长度为 $n+1$ 的数列 $a_1,a_2,\cdots,a_{n+1}$，对于所有的 $i=1,2,\cdots,n+1$，$a_i$ 要么是一个在区间 $[0,n)$ 内的整数，要么是 $n^2$。现在给定 $n$ 和 $S=\sum\limits_{i=1}^{n+1} a_i$，请求出数列中所有等于 $n^2$ 的元素个数。 数据保证存在一个合法的数列，使得数列中所有元素的和等于 $S$。并且可以发现，答案在限制条件下唯一。 数据范围： - $t$ 组数据，$1\leqslant t\leqslant 2\times 10^4$。 - $1\leqslant n\leqslant 10^6$，$0\leqslant S\leqslant 10^{18}$。 Translated by Eason_AC

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

4
7 0
1 1
2 12
3 12

输出样例 #1

0
1
3
1

说明

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.