Coin Jam (Large)

문제

잼코인은 $N \ge 2$ 자리 문자열로 다음 성질을 모두 만족한다.

모든 자리는 0 또는 1이다.
첫 자리와 마지막 자리는 1이다.
이 문자열을 2진법부터 10진법까지 어느 진법으로 해석해도 그 수는 소수가 아니다.

0과 1로 이루어진 문자열이 모두 잼코인은 아니다. 예를 들어 101은 2진법으로 해석하면 소수 5이므로 잼코인이 아니다. 반면 1001은 잼코인이다. 2진법부터 10진법까지 해석한 값은 차례로 9, 28, 65, 126, 217, 344, 513, 730, 1001이고, 이 중 소수는 없다.

잼코인을 화폐처럼 쓰는 공동체가 있다고 한다. 누군가에게 잼코인을 보낼 때는 2진법부터 10진법까지 각 진법으로 해석한 값의 자명하지 않은 약수를 함께 보내 그 잼코인이 진짜임을 증명하는 것이 예의다. 양의 정수 $K$ 의 자명하지 않은 약수란 $K$ 를 나누어떨어지게 하는 양의 정수 중 1과 $K$ 가 아닌 수다. 약수는 모두 10진법으로 적는다.

이 문제에서는 증명에 쓰는 약수의 크기를 제한한다. 길이가 $N$ 인 잼코인 중에서 2진법부터 10진법까지 모든 진법에 대해 해석한 값 $K_b$ 가 1000 이하의 자명하지 않은 약수를 가지는 것을 검증 가능한 잼코인이라고 하자.

길이가 $N$ 인 검증 가능한 잼코인을 작은 것부터 $J$ 개 구하고, 각 잼코인이 진짜라는 증명을 함께 출력하시오. 길이가 같은 두 문자열의 크기는 2진수로 읽은 값으로 비교하며, 이는 사전순 비교와 같다. 증명으로는 각 진법 $b$ 에 대해 $K_b$ 의 자명하지 않은 약수 중 가장 작은 것을 출력한다.

입력

첫째 줄에 테스트 케이스의 수 $T$ 가 주어진다. 이어서 $T$ 개의 테스트 케이스가 주어지며, 각 테스트 케이스는 두 정수 $N$ 과 $J$ 가 적힌 한 줄이다.

제한

$T = 1$
$2 \le N \le 32$
$1 \le J \le 500$
길이가 $N$ 인 검증 가능한 잼코인이 적어도 $J$ 개 존재하는 입력만 주어진다.

출력

각 테스트 케이스마다 $J+1$ 줄을 출력한다. 첫 줄에는 Case #x:만 출력하며, x는 1부터 시작하는 테스트 케이스 번호다. 다음 $J$ 줄에는 길이가 $N$ 인 검증 가능한 잼코인을 작은 것부터 차례로 하나씩 출력하고, 같은 줄에 공백으로 구분한 정수 9개를 이어서 출력한다. 9개 중 $i$ 번째 정수는 그 잼코인을 $i+1$ 진법으로 해석한 값의 자명하지 않은 약수 중 가장 작은 것이다.

$J$ 개의 잼코인은 모두 서로 달라야 한다.

힌트

예제는 설명을 쉽게 하려고 $N$ 과 $J$ 를 아주 작게 잡았다. 길이가 6이고 1로 시작하고 끝나는 문자열을 작은 것부터 보면 다음과 같다.

100001은 잼코인이다. 2진법으로 해석하면 $33 = 3 \times 11$ 이므로 첫 번째 약수는 3이다. 3진법으로 해석하면 244이고 가장 작은 자명하지 않은 약수는 2다.
100011은 잼코인이다. 2진법으로 해석한 값은 35이고, 1과 35는 자명한 약수이므로 쓸 수 없다. 가장 작은 자명하지 않은 약수는 5다.
100101은 2진법으로 해석하면 소수 37이므로 잼코인이 아니다.
100111은 잼코인이다. 2진법으로 해석하면 $39 = 3 \times 13$ 이다.

따라서 작은 것부터 세 개는 100001, 100011, 100111이다. 또 110111은 3진법으로 해석하면 $1 \cdot 243 + 1 \cdot 81 + 0 \cdot 27 + 1 \cdot 9 + 1 \cdot 3 + 1 \cdot 1 = 337$ 이고 337은 소수이므로 잼코인이 아니다. 010101은 1로 시작하지 않고 101010은 1로 끝나지 않으므로 둘 다 잼코인이 아니다.