엔트 수

엔트(Ent)는 가운데땅(Middle-earth)에 사는 나무를 닮은 종족으로, 숲을 지키는 오래된 목자들입니다. 빌보가 엔트들을 만나려고 팡고른 숲을 찾았을 때, 그들의 기록에서 아주아주 긴 수들을 발견하고 가장 나이 많은 엔트인 나무수염에게 그 의미를 묻습니다. 나무수염은 이 수들이 어떤 수열들의 수렴 속도를 나타낸다고 설명합니다(이 수열은 로이벤 굿스타인(Reuben Goodstein)이라는 수학자가 엔트들에게 소개한 것입니다). 며칠에 걸친 설명 끝에 빌보는 마침내 이런 수들이 어떻게 만들어지는지 이해하게 됩니다.

두 수 $N$과 $B$로 정의되는 수열을 생각합시다. 수열의 첫 항은 밑 $B$로 나타낸 $N$ 자신입니다. 다음 항을 얻으려면 현재 수를 1 줄인 뒤, 그 결과의 각 자릿수는 그대로 둔 채 밑 $B$를 1 늘립니다.

예를 들어 $N = 42$, $B = 10$에서 시작해 봅시다. 각 자리를 괄호로 묶어 (4)(2) Base 10처럼 씁니다. 다음 항은 (4)(1) Base 11이며, 이는 10진법으로 45입니다. 먼저 1을 빼서 (4)(1) Base 10을 얻고, 자릿수는 그대로 둔 채 밑을 1 늘린 것입니다. 그다음 항은 (4)(0) Base 12, 즉 10진법으로 48입니다. 아래 표는 수열이 어떻게 이어지는지 보여 줍니다.

이렇게 계속 커질 것처럼 보이지만, 이 수열은 결국 밑 $B = 192$에서 0에 도달합니다(항이 (1) Base 191로, 그다음 (0) Base 192로 갑니다). 다음 표는 다른 시작점에 대한 수열을 보여 줍니다. 보다시피 값은 매우 빠르게 커질 수 있습니다(밑 100에서 항은 이미 1000707070428에 이릅니다).

나무수염은 이 수열이 처음에는 엄청나게 큰 값으로 치솟더라도 언제나 0에 도달한다고 설명합니다. 빌보는 이를 믿기 어려워하며 당신의 도움을 청합니다. 두 시작 수 $N$과 $B$가 주어질 때, 밑이 $2^{60}$(빌보가 상상할 수 있는 거의 가장 큰 수)에 이르기 전에 수열이 0에 도달하는지, 도달한다면 어느 밑에서 0이 되는지 판정하세요.

첫 줄에 테스트 케이스의 수 $T$가 주어집니다($T < 100$). 이어지는 $T$개의 각 줄에는 시작 수 $N$과 시작 밑 $B$($B \ge 2$)가 공백 하나로 구분되어 주어집니다.

각 테스트 케이스마다 한 줄을 출력합니다. 밑이 $2^{60}$에 이르기 전에 수열이 0에 도달하면 다음을 출력합니다.

Starting with N = <N> and B = <B>, sequence converges to 0 at Base <base>.

여기서 <base>는 항이 처음으로 0이 되는 밑입니다. 그렇지 않으면 다음을 출력합니다.

Starting with N = <N> and B = <B>, sequence did not converge to 0 before 2^60.