D. Problemsolving Marathon
*special; binary search; greedy
Polycarp has decided to do a problemsolving marathon. He wants to solve \(s\) problems in \(n\) days. Let \(a_i\) be the number of problems he solves during the \(i\)-th day. He wants to find a distribution of problems into days such that: \(a_i\) is an integer value for all \(i\) from \(1\) to \(n\); \(a_i \ge 1\) for all \(i\) from \(1\) to \(n\); \(a_{i + 1} \ge a_i\) for all \(i\) from \(1\) to \(n-1\); \(a_{i + 1} \le 2 \cdot a_i\) for all \(i\) from \(1\) to \(n-1\); \(a_n\) is maximized. Note that \(a_1\) can be arbitrarily large.What is the largest value of \(a_n\) Polycarp can obtain?
The first line contains a single integer \(t\) (\(1 \le t \le 1000\)) — the number of testcases.Then the descriptions of \(t\) testcases follow.The only line of each testcase contains two integers \(n\) and \(s\) (\(1 \le n \le s \le 10^{18}\)) — the number of days and the number of problems Polycarp wants to solve.It's guaranteed that the distribution always exists within the given constraints.
For each testcase print a single integer — the maximum value of \(a_n\).
In the first testcase there is only one distribution: \([15]\).In the second testcase the distribution that maximizes \(a_n\) is: \([2, 3, 4]\).In the third testcase the distribution that maximizes \(a_n\) is: \([2, 4]\). \([3, 3]\) is a valid distribution but \(a_n=3\) which is smaller than \(4\). \([1, 5]\) is not a valid distribution because \(5 > 2 \cdot 1\).