Healthy Howard Hamlin#12928

Healthy Howard Hamlin

1 second
256 megabytes
Easy

Howard Hamlin likes to run. He decided that he is going to run for consecutive minutes today.

Howard can run in two modes: slow and fast. The following conditions hold:

Howard wants to run in fast mode as much as possible. What's the largest number of minutes out of all minutes that Howard could spend running in a fast mode?

Input

The first line contains a single integer (1 \le t \le 10^5)  — the number of test cases. The description of test cases follows.

The only line of each test case contains two integers (1 \leq B \leq A \leq 10^9).

Output

For each test case, output a single integer  — the largest number of minutes out of all minutes that Howard could spend running in a fast mode.

Examples

Example

Loading
Loading

Note

In the first test case, Howard can run for the first minute in the fast mode, then run for the second minute in the slow mode, and then run for the third minute in fast mode again.

In the second test case, Howard can run for all minutes in the fast mode.