Anyone that ever went to men's restroom knows about International Choice of Urinal Protocol. It reads as follows:

This protocol specifies the rules of choosing a urinal, for a given row of urinals (some of them may be already taken).

• One should choose a urinal that maximizes the distance to the closest urinal that is already taken.
• If there is more than one urinal satisfying the condition above, one should choose a urinal that is the farthest from the door.
• One must not take a urinal that is adjacent to an already taken urinal. This rule is introduced in order to avoid Awkwardness.

There is a row of n urinals, numbered with consecutive integers, from left to right, starting with 1. The door is located to the right of the urinal number n. At first, the restroom is empty. Let's assume that people are coming in, one by one, taking the urinals according to the Protocol, without freeing them up in the meantime. Which urinal will be chosen by the k-th person?

Input

The first line contains a single integer t, denoting the number of testcases. Then, testcases follow.

One testcase is a single line, containing two natural numbers n and k.

(1 <= k <= n <= 10¹⁸)

Output

For every testcase you should print one line containing the number that corresponds to a urinal taken by the k-th person coming to the restroom with n urinals. If there is no way for that person to pick a urinal without violating the Protocol, you should print "OOPS" instead.

Example

Input:

10
5 1
5 2
5 3
5 4
5 5
9 5
9 6
19 8
23 6
27 12

Output:

1
5
3
OOPS
OOPS
7
OOPS
12
9
OOPS