Coin Jam (Small)

A jamcoin is a string of $N \ge 2$ digits with the following properties:

• Every digit is either 0 or 1.
• The first digit is 1 and the last digit is 1.
• If you interpret the string in any base between 2 and 10, inclusive, the resulting number is not prime.

Not every string of 0s and 1s is a jamcoin. For example, 101 is not a jamcoin: its interpretation in base 2 is 5, which is prime. But the string 1001 is a jamcoin. In bases 2 through 10, its interpretation is 9, 28, 65, 126, 217, 344, 513, 730, and 1001, respectively, and none of those is prime.

We hear that there may be communities that use jamcoins as a form of currency. When sending someone a jamcoin, it is polite to prove that the jamcoin is legitimate by including a nontrivial divisor of that jamcoin's interpretation in each base from 2 to 10. A nontrivial divisor of a positive integer $K$ is a positive integer other than 1 or $K$ that evenly divides $K$. These divisors must be expressed in base 10.

For example, for the jamcoin 1001 above, one possible set of nontrivial divisors for its interpretations in bases 2 through 10 is 3, 7, 5, 6, 31, 8, 27, 5, and 77, respectively.

Produce $J$ different jamcoins of length $N$, along with proof that they are legitimate. So that the answer is unique, follow the rules described in the Output section.

The first line of the input gives the number of test cases, $T$. $T$ lines follow; each contains one test case with two integers $N$ and $J$.

Limits

• $1 \le T \le 10$
• $2 \le N \le 16$
• $1 \le J \le 50$
• It is guaranteed that at least $J$ distinct jamcoins of length $N$ exist.

For each test case, output $J+1$ lines. The first line must consist of only Case #x:, where x is the test case number (starting from 1). Each of the next $J$ lines must consist of a jamcoin of length $N$ followed by nine integers, separated by spaces. The $i$-th of those nine integers (counting from 1) must be a nontrivial divisor of the jamcoin when the jamcoin is interpreted in base $i+1$.

To make the answer unique, follow these rules:

• Output the $J$ lexicographically smallest jamcoins of length $N$, in lexicographic order. Because all of them have the same length, this is the same as the $J$ jamcoins with the smallest base 2 values, in increasing order.
• For each base, output the smallest nontrivial divisor of the interpreted value, which is its smallest prime factor.

All jamcoins in the output must be different.

The sample uses very small values of $N$ and $J$ for ease of explanation.

• In lexicographic order, the jamcoins of length 6 begin 100001, 100011, 100111, and so on. 100101 is not a jamcoin: in base 2 it is 37, which is prime.
• 110111 is not a jamcoin either. In base 3 it is $1 \times 243 + 1 \times 81 + 0 \times 27 + 1 \times 9 + 1 \times 3 + 1 \times 1 = 337$, and 337 is prime.
• 10101 is a jamcoin, but 010101 is not, because jamcoins begin with 1.
• 101010 is not a jamcoin, because jamcoins end with 1.
• 100011 is $35 = 5 \times 7$ in base 2. The numbers 1 and 35 are trivial divisors, and 7 is not the smallest nontrivial divisor, so the number right after 100011 is 5.