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 can run in fast mode for at most minutes in a row;
After Howard ran in a fast mode for some time, he has to rest for at least the same amount of time. More formally, if Howard ran for minutes in a row in fast mode and switched to the slow mode, he won't be able to run in fast mode for at least next minutes;
Howard can only switch running modes at integer points in time.
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?
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).
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.
Example
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.