The chairman of the T Association, Big G, has decided to select a Little g to succeed him as the chairman of the T Association. To ensure fairness, he has appointed Little c to oversee the process.

Given that there are not many Little gs in the T Association, Little c has decided to determine the winner in the simplest way possible: let the $n$ Little gs compete against each other in a series of matches where there are no draws. The winner of each match receives one point, and the loser receives zero points.

After the matches concluded and the scores were tallied, Little c discovered the "$z$-gg Law" regarding these $\frac{n(n-1)}{2}$ matches: in any group of $z+1$ Little gs, there always exists one Little g who can defeat the other $z$ Little gs, and simultaneously there exists another Little g who is defeated by the other $z$ Little gs.

Due to some mysterious factors from the T Association, Little c suddenly wants to know the minimum number of distinct scores possible among the $n$ Little gs in all match outcomes that satisfy the aforementioned "$z$-gg Law." Since Little c is busy (not particularly smart) with counting the data, she has decided to leave this problem for you to answer.

Input

The input is read from standard input.

There are multiple test cases.

The first line contains an integer $T$ ($1 \le T \le 3 \times 10^5$), representing the number of test cases.

Each of the next $T$ lines contains two positive integers $n$ and $z$ ($1 \le z < n \le 10^{18}$), as described in the problem statement.

Output

Output to standard output.

For each test case, output a single positive integer on a new line representing the answer.

Examples

Input 1

5
2 1
3 1
3 2
4 1
4 3

Output 1

2
1
3
2
4

Note 1

For $n=2, z=1$, it is clear that one Little g must have a score of $1$ and the other $0$, so the answer is $2$.

For $n=3, z=1$, the matches $1 \to 2, 2 \to 3, 3 \to 1$ (where $a \to b$ means "$a$ defeats $b$") satisfy the law, and everyone's score is $1$, so the answer is $1$.

For $n=3, z=2$, by symmetry and the problem's law, assume $1$ and $3$ are the overall winner and loser among the $3$ Little gs. Then the matches must be $1 \to 2, 1 \to 3, 2 \to 3$. The scores of the three are $2, 1, 0$, so the answer is $3$.

For $n=4, z=1$, in the matches $1 \to 3, 1 \to 4, 2 \to 1, 2 \to 3, 3 \to 4, 4 \to 2$, the scores of the four are $2, 2, 1, 1$. Since the sum of the scores $\frac{4 \times 3}{2} = 6$ is not a multiple of $4$, it is impossible for all four scores to be identical, so the answer is $2$.

For $n=4, z=3$, assuming $1$ and $4$ are the overall winner and loser, the sum of the scores of $2$ and $3$ is $6 - 3 - 0 = 3$. Thus, their scores must be $2, 1$ or $3, 0$. Since it is impossible to have two people with a score of $3$, the scores of $2$ and $3$ must be $2, 1$, so the answer is $4$.

Input 2

6
7 1
7 2
7 3
7 4
7 5
7 6

Output 2

1
7
7
7
5
3

Note

This problem is not difficult.