G. Graph and Information Delivery
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

SnowballSH has installed $$$n$$$ computers and wants to transmit information between them.

With one wire, SnowballSH can connect two computers. When a computer receives some information, it will automatically transmit it to all computers connected to it by a wire in exactly $$$1$$$ second.

SnowballSH wants to make sure that it is possible to deliver information from any computer to every other computer in at most $$$k$$$ seconds. However, he also wants to minimize the number of wires he needs to buy.

Please help SnowballSH determine the minimum number of wires he needs.

Input

Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases.

The first (and only) line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n, k \le 10^9$$$) — the number of computers and the maximum allowed time for information on a computer to reach every other computer.

Output

For each test case, print one integer — the minimum number of wires SnowballSH needs.

Example
Input
3
3 1
5 3
1 1000000000
Output
3
4
0
Note

For the first test case, SnowballSH can use three wires to connect computer 1 and computer 2, computer 2 and computer 3, and computer 3 and computer 1. It can be shown that it is not possible to transmit information from any computer to any other computer in at most $$$1$$$ second using less than $$$3$$$ wires.