장식하는 세제곱러버

키파는 세제곱수를 엄청나게 좋아한다. 그걸 잘 알고 있던 모리는 생일 선물로 $n^3$개의 동일한 조각으로 잘려 있는 커다랗고 동그란 케이크를 키파에게 선물했다. 각 조각은 맛이 모두 다르다. 문제가 있다면, 이 케이크는 너무 커서 먹기 위해서 조각 위에 올라가서 먹어야 한다는 것이다!

케이크 조각 위에 올라선 키파는 눈이 나빠서 현재 케이크 조각과 양 옆의 케이크 조각밖에 볼 수 없다. 키파는 먼저 모든 조각을 시계 방향으로 맛보면서 1번부터 $n$번까지 $n$가지의 장식 중 하나를 올려서, 어느 위치에 있어도 현재 조각이 무엇인지 알 수 있도록 하고 싶다. $n^3$이나 되는 수를 정확히 세는 건 어려우니까.

키파는 처음에 피로도 0, 잠정 피로도 1을 가진 채 특정 조각에 서 있다. 시계 방향으로 한 조각을 건너뛸 때마다 잠정 피로도는 $n$배 증가한다. 또, 조각이 너무 넓기 때문에 한 조각에는 장식을 $i$번 장식 한 가지 종류만 놓고, 놓을 때마다 $i$에 잠정 피로도를 곱한 값만큼 피로도가 더해진다.

모든 장식을 놓고 한 바퀴 돌아 시작 위치로 왔을 때 피로도가 최소가 되도록 장식을 배치할 때, 시작 위치로부터 시계 방향으로 $p$번째 조각에는 무슨 장식을 놓았을지 출력하는 프로그램을 작성해서 키파를 도와 줍시다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. $T$는 $10^5$ 이하의 양의 정수이다.

둘째 줄부터 $T$개의 줄마다 $10^6$ 이하의 양의 정수 $n$과 $n^3$ 이하의 양의 정수 $p$가 공백을 사이에 두고 주어진다.

$T$개의 줄에 시작 위치에서 시계 방향으로 $p$번째 조각에 올려진 장식의 번호를 출력한다.

장식은 총 2개가 있으며, 모든 조각이 구분 가능하도록 올리는 방법은 16가지가 있다.

그중 2번, 2번, 2번, 1번, 2번, 1번, 1번, 1번 순으로 올리는 것이 최종 피로도가 278로 가장 작다.