URI - Urinals

no tags 

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 <= 1018)

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

hide comments
Oleg: 2023-09-07 04:35:30

See also: https://www.spoj.com/problems/OGLEDALA/

akku_g: 2020-10-24 21:13:39

i cracked the solution when n is even..but i m unable to find solution when n is odd...because of the problem arising in test case 23 6...kindly someone help me with this part...a little help will be appreciated....thanking in advance...

ferol: 2016-11-14 10:21:05

for 10 3 solution is 3 or 7?

:D: 2016-10-16 02:01:58

Nice problem. Practical as well :)

[Rampage] Blue.Mary: 2016-10-14 15:26:27

My AC program uses long long in C++ only.

Poog: 2016-10-14 13:30:25

Do this need big integers?


Added by:Piotr Jagiełło
Date:2016-10-13
Time limit:1s-3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU
Resource:own problem, inspired by XKCD blog post