← 返回题目列表

Codeforces · 1488/D

D. 解决问题马拉松

中文机器翻译题面 查看原题

波利卡普决定举办一场解决问题的马拉松比赛。他想在 $$$n$$$ 天内解决 $$$s$$$ 问题。令 $$$a_i$$$ 为他在第 $$$i$$$ 天解决的问题数量。他希望找出问题在几天内的分布情况,以便:

- $$$a_i$$$ 是从 $$$1$$$ 到 $$$n$$$ 的所有 $$$i$$$ 的整数值;
- $$$a_i \ge 1$$$ 对于从 $$$1$$$ 到 $$$n$$$ 的所有 $$$i$$$;
- $$$a_{i + 1} \ge a_i$$$ 对于从 $$$1$$$ 到 $$$n-1$$$ 的所有 $$$i$$$;
- $$$a_{i + 1} \le 2 \cdot a_i$$$ 对于从 $$$1$$$ 到 $$$n-1$$$ 的所有 $$$i$$$;
- $$$a_n$$$ 已最大化。

请注意,$$$a_1$$$ 可以任意大。

$$$a_n$$$ Polycarp 可以获得的最大值是多少?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 1000$$$) — 测试用例的数量。

然后是 $$$t$$$ 测试用例的描述。

每个测试用例的唯一行包含两个整数 $$$n$$$ 和 $$$s$$$ ($$$1 \le n \le s \le 10^{18}$$$) — Polycarp 想要解决的天数和问题数量。

保证分布始终存在于给定的约束范围内。

输出

对于每个测试用例,打印一个整数 - $$$a_n$$$ 的最大值。

示例

输入 #1

3
1 15
3 9
2 6

输出 #1

15
4
4

注意

在第一个测试用例中只有一个分布:$$$[15]$$$。

在第二个测试用例中,最大化 $$$a_n$$$ 的分布是:$$$[2, 3, 4]$$$。

在第三个测试用例中,最大化 $$$a_n$$$ 的分布是:$$$[2, 4]$$$。 $$$[3, 3]$$$ 是有效分布,但 $$$a_n=3$$$ 小于 $$$4$$$。 $$$[1, 5]$$$ 不是有效的分布,因为 $$$5 > 2 \cdot 1$$$。