Malvika conducts a Programming Camp

Time limit1sMemory limit1024 MB

Summary

Find the minimum hours for n people in a line to learn m topics, where Malvika at the end teaches and each hour one neighbour teaches another.

Level: Medium6 of 10
Topics: Math, Greedy
Solved: No attempts yet

Statement

Malvika has gained a lot of knowledge from programming contests. She wants to use it to train the next generation of Indian programmers, so she holds a programming camp. There are $n$ people in a discussion session: $n-1$ students and Malvika herself. They sit in a line from left to right, numbered 1 to $n$ . Malvika sits in spot $n$ . She wants to teach $m$ topics of competitive programming to the students. All the participants are newbies. At the start, the first $n-1$ people know none of the topics, and the $n$ th person (Malvika) knows all of them.

It takes one hour for a person to learn a topic from a neighbour. One person cannot teach and learn during the same hour. In any hour, a person can either teach a topic he knows to one of his neighbours, learn a topic from one of his neighbours, or sit idle. If person $x$ is learning from person $y$ in some hour, then person $y$ must be teaching person $x$ in that same hour. People can work in parallel. For example, while the 4th person teaches the 3rd person, the 1st person can teach the 2nd person or learn from the 2nd person.

Find the minimum number of hours needed for every person to learn all $m$ topics.

Input

The first line contains a single integer $T$ , the number of test cases. Each test case is one line with two space-separated integers $n$ and $m$ , as defined in the statement.

Output

For each test case, print a single integer on its own line: the answer to the problem.

Constraints

$1 \le T, n, m \le 100$

Hint

In the first example there are two people. The second person is Malvika and she has to teach only one topic to the first person. This takes one hour.

In the second example there are three people. The 3rd person is Malvika and she has to teach two topics to the 1st and 2nd persons. In the 1st hour, she teaches the 1st topic to the 2nd person. In the 2nd hour, the 2nd person teaches the 1st topic to the 1st person. In the 3rd hour, Malvika teaches the 2nd topic to the 2nd person. In the 4th hour, the 2nd person teaches that topic to the 1st person. So the total is 4 hours.

Examples1

Example 1
Input
```
2
2 1
3 2
```
Expected output
```
1
4
```