给你两个正整数 $$$n$$$ 和 $$$s$$$。找到 $$$n$$$ 非负整数(不一定不同)数组的最大可能中位数,使其元素之和等于 $$$s$$$。
长度为 $$$m$$$ 的整数数组的中位数是其元素非递减排序中位于 $$$\lceil {\frac{m}{2}} \rceil$$$ 第(向上舍入)位置的数字。职位编号从 $$$1$$$ 开始。例如,数组 $$$[20,40,20,50,50,30]$$$ 的中位数是 $$$[20,20,30,40,50,50]$$$ 的第 $$$\lceil \frac{m}{2} \rceil$$$ 个元素,因此它是 $$$30$$$。中位数还存在其他定义,但在这个问题中我们使用所描述的定义。
输入
输入由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例包含一行,其中包含两个整数 $$$n$$$ 和 $$$s$$$ ($$$1 \le n, s \le 10^9$$$) - 数组的长度和所需元素的总和。
输出
对于每个测试用例,打印一个整数 - 最大可能的中位数。
示例
输入 #1
8 1 5 2 5 3 5 2 1 7 17 4 14 1 1000000000 1000000000 1
输出 #1
5 2 2 0 4 4 1000000000 0
注意
前三个测试用例的可能数组(在每个数组中,中位数带有下划线):
- 在第一个测试用例中 $$$[\underline{5}]$$$
- 在第二个测试用例中 $$$[\underline{2}, 3]$$$
- 在第三个测试用例中 $$$[1, \underline{2}, 2]$$$