수비학

많은 문화권에서 특정 숫자는 특별한 의미를 지닌다. 예를 들어 666은 흔히 악마와, 777은 행운과 연결된다. 이런 숫자들은 보기에 일정한 무늬(패턴)를 이루는 경향이 있어서, 다음번 의미 있는 숫자를 찾으려는 수비학자는 이런 패턴을 알아채는 데 관심이 많다.

어떤 수는 알맞은 진법으로 표기했을 때에만 흥미로운 패턴을 드러낸다. 예를 들어 666을 16진법으로 쓰면 29a가 되어 10진법 표기보다 훨씬 밋밋하다. 과거의, 어쩌면 외계의 문명이 사용했을 온갖 진법을 모두 고려하기 위해, 어떤 수를 특정 진법으로 표기했을 때 관심 있는 패턴과 일치하는지를 검사하려고 한다.

수를 $b$진법으로 바꾼 결과를 기호들의 수열 $S = \langle s_1, s_2, \dots, s_L \rangle$로 나타내자. 각 기호는 그 진법에서의 자릿값을 나타내는 정수이며, 가장 큰 자리부터 차례로 나열한다. 예를 들어 10진수 10을 2진법으로 쓰면 $1010$이므로 $S = \langle 1, 0, 1, 0 \rangle$이고 $L = 4$이다.

패턴은 ab와 같은 문자열이다. 수열 $S$가 패턴 $p$와 일치한다는 것은 다음 두 조건이 모두 성립함을 뜻한다.

1. $L$이 $p$의 길이 이상이다.
2. $p$에 등장하는 서로 다른 문자들과 $S$에 등장하는 서로 다른 기호들 사이에 일대일 대응이 존재하여, $p$를 반복해 이어 붙인 뒤 길이가 $L$이 되도록 자른 문자열 $r$의 각 문자를 대응되는 기호로 바꾸면 정확히 $S$가 된다.

이 정의에 따르면 10을 2진법으로 쓴 값은 패턴 ab와 일치한다(a$\to$1, b$\to$0으로 대응하면 abab가 $\langle 1, 0, 1, 0 \rangle$이 된다).

첫 번째 줄에는 데이터 집합의 개수 $K$가 주어진다. 이어지는 $K$개의 줄에는 각각 양의 정수 $n$과 문자열 $p$가 주어지며, $n$은 관심 있는 수, $p$는 맞춰 볼 패턴이다. $n$은 64비트 정수 범위 안에 들어가고, $p$의 길이는 최대 10이며, $p$의 각 문자는 소문자 a부터 j까지 중 하나이다.

각 데이터 집합마다 먼저 Data Set x:를 한 줄에 출력한다. 여기서 $x$는 데이터 집합의 번호이며 1부터 시작한다. 그다음, $n$을 $b$진법으로 썼을 때 패턴 $p$와 일치하는 가장 작은 진법 $b$($2 \le b \le 1000000$)를 출력한다. 다음 줄에는 그 일치하는 수열의 정수 기호들을 하나의 공백으로 구분하여 출력하며, 줄 끝에 공백을 남기지 않는다. 범위 안의 어떤 진법으로도 일치하지 않으면 진법과 수열 대신 No such base.를 출력한다. 서로 다른 데이터 집합 사이는 빈 줄로 구분한다.