시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 97 32 12 38.710%

문제

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

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

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

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

입력

첫째 줄에 테스트 케이스의 수 T가 주어집니다. T는 105 이하의 양의 정수입니다.

둘째 줄부터 T개의 줄마다 106 이하의 양의 정수 nn3 이하의 양의 정수 p가 공백을 사이에 두고 주어집니다.

출력

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

예제 입력 1

3
2 1
2 4
2 6

예제 출력 1

2
1
1

노트

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

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

출처

Contest > 키파컵 > 제1회 키파컵 D번

  • 문제를 만든 사람: kipa00