Decorator Cubelover

Kipa loves perfect cubes more than anything. Mori, who knew this well, gave Kipa a large round cake cut into $n^3$ identical pieces as a birthday present. Every piece tastes different. There is one problem: the cake is so large that to eat it you have to climb on top of the pieces!

Standing on a cake piece, Kipa has poor eyesight and can see only the current piece and the pieces on either side. Kipa first wants to taste every piece in clockwise order and place one of $n$ decorations, numbered 1 through $n$, so that no matter where Kipa stands, the current piece can be identified. Counting exactly $n^3$ pieces by eye is hard.

Kipa starts standing on a particular piece with fatigue 0 and tentative fatigue 1. Each time Kipa skips one piece clockwise, the tentative fatigue is multiplied by $n$. Also, because each piece is so wide, a piece holds only one decoration, decoration $i$, and placing it adds $i$ times the tentative fatigue to the fatigue.

Write a program that helps Kipa: when the decorations are arranged so that the fatigue is minimized after placing all decorations and walking one full lap back to the starting position, output which decoration is placed on the $p$-th piece clockwise from the starting position.

The first line gives the number of test cases $T$. $T$ is a positive integer at most $10^5$.

The next $T$ lines each give a positive integer $n$ at most $10^6$ and a positive integer $p$ at most $n^3$, separated by a space.

For each of the $T$ lines, output the number of the decoration placed on the $p$-th piece clockwise from the starting position.

There are 2 decorations in total, and there are 16 ways to place them so that every piece is distinguishable.

Among them, placing them in the order 2, 2, 2, 1, 2, 1, 1, 1 gives the smallest final fatigue, 278.