코인 잼 (Small)

문제

잼코인은 길이가 $N \ge 2$ 인 숫자 문자열 중 다음 조건을 모두 만족하는 것이다.

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

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

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

예를 들어 위의 잼코인 1001에 대해 2진법부터 10진법까지의 해석값의 자명하지 않은 약수로 차례로 3, 7, 5, 6, 31, 8, 27, 5, 77을 고를 수 있다.

길이가 $N$ 인 서로 다른 잼코인 $J$ 개를 그 증명과 함께 출력하라. 이 문제에서는 답이 하나로 정해지도록 출력 형식에서 설명하는 규칙을 따라야 한다.

입력

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

제한

$1 \le T \le 10$
$2 \le N \le 16$
$1 \le J \le 50$
길이가 $N$ 인 서로 다른 잼코인이 적어도 $J$ 개 존재함이 보장된다.

출력

각 테스트 케이스마다 $J+1$ 개의 줄을 출력한다. 첫 줄에는 Case #x:만 출력한다. x는 1부터 시작하는 테스트 케이스 번호다. 나머지 $J$ 개의 줄에는 각각 길이가 $N$ 인 잼코인 하나와 정수 9개를 공백으로 구분해 출력한다. 9개 중 $i$ 번째 정수( $i$ 는 1부터 센다)는 그 잼코인을 $i+1$ 진법으로 해석한 값의 자명하지 않은 약수여야 한다.

답이 하나로 정해지도록 다음 규칙을 따른다.

길이가 $N$ 인 잼코인 중 사전순으로 가장 앞선 $J$ 개를 사전순으로 출력한다. 길이가 모두 같으므로 이는 2진법으로 해석한 값이 가장 작은 $J$ 개를 오름차순으로 출력하는 것과 같다.
각 진법마다 해석한 값의 자명하지 않은 약수 중 가장 작은 것을 출력한다. 이 값은 해석한 값의 가장 작은 소인수다.

출력하는 잼코인은 모두 서로 달라야 한다.

힌트

예제에서는 설명을 쉽게 하려고 $N$ 과 $J$ 를 작게 잡았다.

길이가 6인 잼코인을 사전순으로 나열하면 100001, 100011, 100111, ... 순이다. 100101은 2진법으로 해석하면 37이고 37은 소수이므로 잼코인이 아니다.
110111도 잼코인이 아니다. 3진법으로 해석하면 $1 \times 243 + 1 \times 81 + 0 \times 27 + 1 \times 9 + 1 \times 3 + 1 \times 1 = 337$ 이고 337은 소수다.
10101은 잼코인이지만 010101은 1로 시작하지 않으므로 잼코인이 아니다.
101010은 1로 끝나지 않으므로 잼코인이 아니다.
100011을 2진법으로 해석하면 $35 = 5 \times 7$ 이다. 1과 35는 자명한 약수이고 7은 가장 작은 약수가 아니므로 100011 바로 다음에는 5를 출력한다.