C. Poniendo aristas
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

It's your first time visiting Bratislava, and because your reputation as a good programmer precedes you, the mayor of Bratislava appoints you to solve a problem.

Bratislava has $$$n$$$ villages, but there are no roads connecting any two villages. In other words, you cannot travel from one village to another; each village is initially isolated. Building roads is expensive, so the mayor has a maximum budget that allows for constructing up to $$$m$$$ roads.

Your task is to minimize the maximum possible distance between all the villages.

Input

The first line will consist of a single natural number $$$t$$$, ($$$1 \le t \le 10^5$$$) — the number of test cases.

The first line of each test case contains the natural numbers $$$n$$$ and $$$m$$$, ($$$2 \le n \le 5 \cdot 10^8$$$, $$$0 \le m \le 5 \cdot 10^8$$$).

Output

For each test case, print the minimum maximum distance if Bratislava has $$$n$$$ villages and you can build $$$m$$$ roads. If it is impossible to connect all the villages, print $$$-1$$$.

Example
Input
3
3 2
4 8
11 2
Output
2
1
-1