E. Car Factory
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In a car factory each car needs to go through k stages in order to be ready for sale, and each stage needs one day to be completed.

The process in the factory goes as follows. On the first day a car enters the first stage. On the second day a car moves from the first stage to the second stage, and a new car enters the first stage. On the third day a car moves from the second stage to the third stage, a car moves from the first stage to the second stage, and a new car enters the first stage, and so on. After k days (i.e. k stages) the car will be ready for sale.

Your task is simple, given the number of stages for each car to be ready, and the number of cars to be manufactured. How many days are needed to finish manufacturing all the cars?

Input

The first line of the input contains an integer T (1  ≤  T  ≤  1000), where T is the number of the test cases.

Each test case has one line that contains two integers n and k (1  ≤  n, k  ≤  109), the number of cars to be manufactured and the number of stages each car requires.

Output

For each test case, print a single integer that represents the number of required days to manufacture all the cars.

Examples
Input
4
1 1
2 3
4 3
14526 78965
Output
1
4
6
93490
Note

Let's solve the third case to show how the process goes in the factory:

  • First day: The first car will enter the first stage.
  • Second day: The first car will move to the second stage, and the second car will enter the first stage.
  • Third day: The first car will move to the third stage, the second car will move to the second stage, and the third car will enter the first stage. At the end of this day the first car will be ready for sale.
  • Fourth day: The second car will move to the third stage, the third car will move to the second stage, and the fourth car will enter the first stage. At the end of this day the second car will be ready for sale.
  • Fifth day: The third car will move to the third stage, and the fourth car will move to the second stage. At the end of this day the third car will be ready for sale.
  • Sixth day: The fifth car will move to the third stage. At the end of this day the fourth car will be ready for sale.