1488D · Problemsolving Marathon

Problem: 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?

Input Format: 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.

Output Format: For each testcase print a single integer — the maximum value of $a_n$.

Note: 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$.