34402번 - 2vs2 배스킨라빈스 31

문제

제31회 PIMM 게임 대회를 맞아 '배스킨라빈스 31' 게임을 진행하기로 했다. 하지만 이 게임은 필승법을 아는 사람이 너무 많기 때문에 규칙을 조금 변형하기로 했다.

게임 규칙은 다음과 같다.

1. 게임은 2vs2 팀전으로 네 자리의 원형 탁자에서 진행된다. 각 자리는 시계 방향 순서대로 1번부터 4번까지 번호가 붙어있으며 자리에 앉은 대로 차례가 정해진다.
2. 차례는 1번 자리 → 2번 자리 → 3번 자리 → 4번 자리 → 다시 1번 자리 → 2번 자리 ... 순으로 원형으로 돌아가며 진행된다.
3. 게임이 시작되면 참가자들에게 두 개의 정수 $N$과 $K$가 주어진다.
4. 게임의 참가자들은 차례에 맞춰 1ドル$부터 $N$까지의 수를 순차적으로 부른다.
5. 자기 차례에는 1ドル$개에서 $K$개까지의 수를 연달아 부르고 차례를 넘긴다.
6. 마지막 $N$을 부른 사람이 포함된 팀이 패배하며 반대팀이 승리하고 게임은 종료된다.

당신은 믿음직한 팀원과 함께 이 게임 대회에 참가하기로 결정했다.

최대한 많은 경우에 대비하기 위해서 $T$개의 경우에 대해서 $N$과 $K$가 주어졌을 때 최선의 플레이를 한다고 가정하면 어느 자리에 앉았을 때 항상 승리할 수 있을지 구해보자.

입력

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다.

두 번째 줄부터 $T$개의 줄에 걸쳐 각 테스트 케이스마다 한 줄에 두 개의 정수 $N$과 $K$가 공백으로 구분되어 주어진다.

출력

각 테스트 케이스마다 한 줄에 반드시 이길 수 있는 자리 번호 쌍을 사전 순으로 정렬하여 공백으로 구분하여 모두 출력한다.

자리 번호 쌍은 $(i,j)$ 형식으로 출력한다. 이는 $i$번 자리와 $j$번 자리에 팀이 앉았을 때 최선의 플레이를 한다고 가정하면 항상 승리할 수 있다는 의미이다. 여기서 $i < j$ 여야 한다.

제한

• 1ドル \le T \le 100,000円$
• 1ドル \le N, K \le 10^{18}$

힌트