나눗셈 판별법

Daisy는 최근 정수의 나눗셈 판별법을 배웠고, 그 원리에 매료되었다. 그녀가 배운 판별법 중 하나는 3으로 나누어떨어지는지 확인하는 방법이다. 십진수의 모든 자릿수를 더한 뒤, 그 합이 3으로 나누어떨어지는지 확인하면 된다. 이 합은 원래 수와 3에 대해 같은 나머지를 가진다. 예를 들어 $75 \equiv 7 + 5 \pmod 3$이다. Daisy는 이처럼 나머지를 보존하는 판별법에 특히 관심이 많다.

십진법에는 이 밖에도 같은 성격의 판별법이 있다.

• 11로 나눈 나머지를 구하려면 교대합을 구한다. 마지막 자리(일의 자리)부터 세어 홀수 번째 자리의 숫자는 더하고, 짝수 번째 자리의 숫자는 뺀다. 예를 들어 $123 \equiv 1 - 2 + 3 \pmod{11}$이다.
• 4로 나눈 나머지를 구하려면 마지막 두 자리만 남긴다. 그 값은 원래 수와 4에 대해 합동이다. 예를 들어 $876543 \equiv 43 \pmod 4$이다.
• 7로 나눈 나머지를 구하려면 세 자리씩 묶은 값의 교대합을 구한다. 예를 들어 $4389328 \equiv 4 - 389 + 328 \pmod 7$이다.

다른 진법에서도 비슷한 판별법을 찾을 수 있다. 예를 들어 8진수에서 5로 나눈 나머지를 구하려면 두 자리씩 묶은 값의 교대합을 구한다. 예를 들어 $1234\_8 \equiv -12\_8 + 34\_8 \pmod 5$이다.

Daisy는 주어진 진법 $b$에 대해 이런 규칙을 찾고자 한다. 그녀가 살펴보는 규칙은 세 종류다.

• 1형: 진법 $b$로 표기한 정수의 마지막 $k$ 자리를 취한다.
• 2형: 진법 $b$로 표기한 정수를 $k$ 자리씩 묶은 값들의 합을 취한다.
• 3형: 진법 $b$로 표기한 정수를 $k$ 자리씩 묶은 값들의 교대합을 취한다.

이런 규칙이 항상 존재하지는 않는다. 예를 들어 십진법에는 6으로 나누어떨어지는지 판별하는 규칙이 없다. 6의 배수를 판별하는 다른 방법은 있는데도 말이다.

주어진 진법 $b$와 나눌 수 $n$에 대해, Daisy는 이런 판별 규칙이 존재하는 가장 작은 그룹 크기 $k$를 알고자 한다.

첫 줄에 테스트의 개수 $t$가 주어진다. 이어지는 $t$개의 줄에는 각각 진법 $b$와 나눌 수 $n$이 주어진다 ($b, n \ge 2$). 모든 $b$ 값의 합은 $10^6$을 넘지 않으며, 모든 $n$ 값의 합도 $10^6$을 넘지 않는다.

$t$개의 줄에 테스트마다 답을 출력한다. $b$와 $n$에 대한 판별 규칙이 존재하지 않으면 정수 $0$을 한 개 출력한다. 존재하면 정수 두 개 $a$와 $k$를 출력한다. 여기서 $a$는 규칙의 종류(1, 2, 3 중 하나)이고, $k$는 그룹의 자릿수다. $b$와 $n$에 대해 가능한 모든 판별 규칙 중에서 $k$는 가장 작아야 한다.