I. Cossack Vus and the Treasures

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 $n$ boxes numbered from $1$ to $n$, arranged in a circle. This means boxes $i$ and $i+1$ are adjacent for $1\le i<n$, and boxes $1$ and $n$ are also adjacent. Some of these boxes contain hidden treasures! You can make queries any number of times to gather information.

Query descriptions:

1. Determine the parity (even or odd) of the total number of treasures in any three different boxes.

2. Determine the parity of the total number of treasures in any three consecutive boxes.

Kozak Vus needs to find out:

1. The minimum number of queries of type (1) required to ensure you can determine whether the total number of treasures is even or odd.

2. The minimum number of queries of type (2) 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!

Input

The input consists of several (at least one) test cases.

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

Each of the next $T$ lines contains two integers $n$ and $t$ ($3\le n\le 10^9,1\le t\le 2$).

Output

Output $T$ lines. The $i$-th line should contain a single integer $ans$, where $ans$ is the answer to question number $t$ of the $i$-th test case accordingly.

Examples

Note

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\}$.

Scoring

If the solution works correctly only for $n=3\cdot k$, where $k$ is a positive integer, it will be scored at $25$ points.

If the solution works correctly only for $t=1$, it will be scored at $25$ points.

If the solution works correctly only for $t=2$, it will be scored at $25$ points.