Coin Jam (Large)

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.

There may be communities that use jamcoins as a form of currency. When you send someone a jamcoin, it is polite to prove that the jamcoin is legitimate by including a nontrivial divisor of its 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$. All divisors are written in base 10.

In this problem the size of the proof divisors is limited. Call a jamcoin of length $N$ a verifiable jamcoin if, for every base $b$ from 2 to 10, its interpretation $K_b$ has a nontrivial divisor no greater than 1000.

Find the $J$ smallest verifiable jamcoins of length $N$ and print each one with proof that it is legitimate. Two strings of the same length are compared by their values read in base 2, which is the same as lexicographic order. As proof, print for each base $b$ the smallest nontrivial divisor of $K_b$.

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

Limits

• $T = 1$
• $2 \le N \le 32$
• $1 \le J \le 500$
• At least $J$ verifiable jamcoins of length $N$ exist.

For each test case, output $J+1$ lines. The first line consists of only Case #x:, where x is the test case number (starting from 1). Each of the next $J$ lines contains a verifiable jamcoin of length $N$ followed by nine space-separated integers, with the jamcoins listed in increasing order. The $i$-th of those nine integers (counting from 1) is the smallest nontrivial divisor of the jamcoin interpreted in base $i+1$.

All $J$ jamcoins must be different.

The sample uses very small values of $N$ and $J$ for ease of explanation. Here are the smallest strings of length 6 that begin and end with 1:

• 100001 is a jamcoin. In base 2 it is $33 = 3 \times 11$, so the first divisor is 3. In base 3 it is 244, whose smallest nontrivial divisor is 2.
• 100011 is a jamcoin. In base 2 it is 35. Neither 1 nor 35 can be used because they are trivial divisors; the smallest nontrivial divisor is 5.
• 100101 is not a jamcoin, because in base 2 it is 37, which is prime.
• 100111 is a jamcoin. In base 2 it is $39 = 3 \times 13$.

So the three smallest are 100001, 100011, and 100111. The string 110111 is not a jamcoin: in base 3 it is $1 \cdot 243 + 1 \cdot 81 + 0 \cdot 27 + 1 \cdot 9 + 1 \cdot 3 + 1 \cdot 1 = 337$, and 337 is prime. Neither 010101 nor 101010 is a jamcoin, because jamcoins begin with 1 and end with 1.