ICPC Asia Can Tho Regional Contest 2020

Start

2020-12-10 16:20 AKST

ICPC Asia Can Tho Regional Contest 2020

End

2020-12-10 21:20 AKST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -282 days 18:45:37

Time elapsed

5:00:00

Time remaining

0:00:00

Problem J
Juggling Sequence

The Juggling Sequence is an integer sequence with $n$ elements, defined as follow:

  • $a_1 = 1$,

  • For every $i \geq 1$:

    • If $a_ i \leq i$, then $a_{i+1} = a_ i + i$,

    • If $a_ i > i$, then $a_{i+1} = a_ i - i$.

Let’s sort the juggling sequence in non-decreasing order. What is the $m$-th number?

Input

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

$t$ test cases follow, each test case contains a single line with two integers $n$ and $m$ $(1 \le m \le n \le 10^{18})$.

Output

For each test case, print a single integer — the $m$-th number in the sorted juggling sequence.

Explanation of the sample input

With $n = 6$, the juggling sequence is $1, 2, 4, 1, 5, 10$. After sorting, the sequence becomes $1, 1, 2, 4, 5, 10$.

Sample Input 1 Sample Output 1
3
6 1
6 2
6 6
1
1
10