Base K

We are used to the decimal positional notation for representing numbers, which uses 10 digits, from 0 to 9. However, there is nothing special about 10, and we can just as easily use any other base. For example, base-2 (binary) uses only two digits, 0 and 1, while base-16 (hexadecimal) uses $0$-$9$ and $a, b, c, d, e, f$ (representing ten, eleven, twelve, thirteen, fourteen, and fifteen); both notations are common in computing.

More generally, a base-$k$ representation uses $k$ digits, $0$ through $k - 1$. If a number $n$ is written in base-$k$ as $a_3a_2a_1a_0$, then

$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$

where the subscript $k$ denotes that the number is written in base-$k$. For example,

• $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}$ (here $e$ represents fourteen in base-16)

Given two integers $n$ and $k$, decide whether the base-$k$ representation of $n$ contains every digit from $0$ to $k - 1$.

For example, the base-3 representation of 15 is $120_3$ ($1 \times 3^2 + 2 \times 3^1 + 0 \times 3^0 = 15$), which contains all three digits 0, 1, 2. In contrast, the base-4 representation of 18 is $102_4$ ($1 \times 4^2 + 0 \times 4^1 + 2 \times 4^0 = 18$), which contains only 0, 1, 2 and is missing 3, so it does not contain all digits.

The base-$k$ representation is the standard one, without leading zeros. Therefore the digit 0 must actually appear somewhere in the middle of the number. For instance, 123456789 in base-10 contains only 1 through 9 and no 0, so it does not contain all digits (we do not pad it as 0123456789).

Digits with value 10 or greater are written as lowercase letters: $10 = a$, $11 = b$, $\ldots$, $29 = t$.

The first line contains the number of test cases $T$ ($T < 100$). Each of the next $T$ lines contains one test case: two integers $n$ and $k$, in that order, separated by a space. It is guaranteed that $2 \le k \le 30$ and $0 \le n < 2^{30}$.

For each test case, print one line. Let $r$ be the base-$k$ representation of $n$. If $r$ contains every digit from $0$ to $k - 1$, print

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

Otherwise, print

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

Replace <k>, <n>, and <r> with the actual values.