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?
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})$.
For each test case, print a single integer — the $m$-th number in the sorted juggling sequence.
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 |