The following languages are only available languages for the problems from the contest

Kotlin Heroes: Episode 6:

- Kotlin 1.4.0

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. Problemsolving Marathon

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard 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?

Input

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

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

Example

Input

3 1 15 3 9 2 6

Output

15 4 4

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

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/18/2021 01:38:21 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|