K진법

우리는 수를 나타낼 때 10진 위치 기수법(positional notation)에 익숙하다. 이 표기법은 0부터 9까지 10개의 숫자를 사용한다. 하지만 밑(base)이 반드시 10이어야 할 이유는 없으며, 다른 어떤 밑으로도 똑같이 수를 나타낼 수 있다. 예를 들어 2진법에서는 0과 1 두 개의 숫자만 사용하고, 16진법에서는 $0$-$9$와 $a, b, c, d, e, f$ (각각 10, 11, 12, 13, 14, 15를 나타냄)를 사용한다. 두 표기법 모두 컴퓨터에서 흔히 쓰인다.

일반적으로 $k$진법 표기는 $0$부터 $k - 1$까지 $k$개의 숫자를 사용한다. 수 $n$이 $k$진법으로 $a_3a_2a_1a_0$이라고 적혀 있으면 그 값은 다음과 같다.

$$n = (a_3a_2a_1a_0)_k = a_3 \times k^3 + a_2 \times k^2 + a_1 \times k^1 + a_0 \times k^0$$

여기서 아래 첨자 $k$는 그 수가 $k$진법으로 적혔음을 나타낸다. 예를 들어,

• $465_7 = 4 \times 7^2 + 6 \times 7^1 + 5 \times 7^0 = 243_{10}$
• $46e_{16} = 4 \times 16^2 + 6 \times 16^1 + 14 \times 16^0 = 1134_{10}$ (여기서 $e$는 16진법에서 14를 나타낸다)

두 정수 $n$과 $k$가 주어질 때, $n$의 $k$진법 표기가 $0$부터 $k - 1$까지의 모든 숫자를 포함하는지 판별하라.

예를 들어 15의 3진법 표기는 $120_3$이고 ($1 \times 3^2 + 2 \times 3^1 + 0 \times 3^0 = 15$), 이는 0, 1, 2 세 숫자를 모두 포함한다. 반면 18의 4진법 표기는 $102_4$이며 ($1 \times 4^2 + 0 \times 4^1 + 2 \times 4^0 = 18$), 0, 1, 2만 포함하고 3이 빠져 있으므로 모든 숫자를 포함하지는 않는다.

$k$진법 표기는 앞에 불필요한 0을 붙이지 않는 표준 표기(선행 0 없음)를 사용한다. 따라서 숫자 0은 수의 중간 어딘가에 실제로 나타나야 한다. 예를 들어 10진법의 123456789는 1부터 9까지만 포함하고 0을 포함하지 않으므로 (0123456789처럼 앞에 0을 덧붙여 적지는 않기 때문에) 모든 숫자를 포함하지 않는다.

값이 10 이상인 숫자는 소문자 알파벳으로 표기한다. 즉 $10 = a$, $11 = b$, $\ldots$, $29 = t$이다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다 ($T < 100$). 다음 $T$개의 줄에는 각 테스트 케이스가 한 줄씩 주어지며, 각 줄에는 두 정수 $n$과 $k$가 이 순서대로 공백으로 구분되어 주어진다. $2 \le k \le 30$이고 $0 \le n < 2^{30}$이다.

각 테스트 케이스마다 결과를 한 줄씩 출력한다. $n$의 $k$진법 표기를 $r$이라고 할 때, 그 표기가 $0$부터 $k - 1$까지의 모든 숫자를 포함하면

Base-<k> representation of <n> is <r>; contains all digits.

를 출력하고, 그렇지 않으면

Base-<k> representation of <n> is <r>; does not contain all digits.

를 출력한다. 여기서 <k>, <n>, <r>은 각각 실제 값으로 바꾼다.