D. Problemsolving Marathontime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard outputPolycarp 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?InputThe 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.OutputFor each testcase print a single integer — the maximum value of a_n.ExampleInput
3
1 15
3 9
2 6
Output
15
4
4
NoteIn 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.
3
1 15
3 9
2 6

15 4 4 
['*special problem', 'binary search', 'greedy', '*1900']