Cossack Vus and the Treasures#10258
Kozak Vus decided to buy gifts for his friends. During his shopping trip, he encountered a unique promotion: solve a problem and receive any item for free.
There are boxes numbered from to , arranged in a circle. This means boxes and i+1 are adjacent for 1 \leq i < n, and boxes and are also adjacent. Some of these boxes contain hidden treasures! You can make queries any number of times to gather information.
Query descriptions:
Determine the parity (even or odd) of the total number of treasures in any three different boxes.
Determine the parity of the total number of treasures in any three consecutive boxes.
Kozak Vus needs to find out:
The minimum number of queries of type required to ensure you can determine whether the total number of treasures is even or odd.
The minimum number of queries of type required to ensure you can determine whether the total number of treasures is even or odd.
Help Kozak Vus solve this problem quickly, as the items are disappearing with each passing minute!
The input consists of several (at least one) test cases.
The first line contains a single integer (1 \leq T \leq 10^5) — the number of test cases.
Each of the next lines contains two integers and (3 \leq n \leq 10^9, 1 \leq t \leq 2).
Output lines. The -th line should contain a single integer , where is the answer to question number of the -th test case accordingly.
Example 1
In the second test case, it is sufficient to make the following queries: \{1, 2, 3\}, \{2, 3, 4\}, \{3, 4, 1\}, and \{4, 1, 2\}.
In the third test case, the following queries need to be made: \{1, 3, 5\}, \{3, 5, 4\}, \{3, 5, 2\}.
If the solution works correctly only for n=3 \cdot k, where is a positive integer, it will be scored at points.
If the solution works correctly only for t=1, it will be scored at points.
If the solution works correctly only for t=2, it will be scored at points.