Một jamcoin là một chuỗi gồm \(N\ge2\) chữ số, có các tính chất sau:

• Mọi chữ số là 0 hoặc 1.
• Chữ số đầu là 1 và chữ số cuối là 1.
• Nếu diễn giải chuỗi trong bất kỳ cơ số nào từ 2 đến 10, kể cả hai đầu, số nhận được không phải số nguyên tố.

Không phải mọi chuỗi 0 và 1 đều là jamcoin. Ví dụ, 101 không phải jamcoin vì trong cơ số 2 nó có giá trị 5, là số nguyên tố. Nhưng 1001 là một jamcoin: khi diễn giải lần lượt trong các cơ số từ 2 đến 10, nó có giá trị 9, 28, 65, 126, 217, 344, 513, 730 và 1001; không số nào là nguyên tố.

Chúng tôi nghe nói có những cộng đồng dùng jamcoin làm tiền tệ. Khi gửi jamcoin cho ai đó, phép lịch sự là chứng minh jamcoin hợp lệ bằng cách kèm một ước không tầm thường của giá trị jamcoin trong mỗi cơ số từ 2 đến 10. Ước không tầm thường của số nguyên dương \(K\) là số nguyên dương khác 1 và \(K\), đồng thời chia hết \(K\). Để thuận tiện, các ước phải được viết trong cơ số 10.

Ví dụ, với jamcoin 1001 ở trên, một bộ ước không tầm thường khả dĩ cho các giá trị trong cơ số 2 đến 10 lần lượt là 3, 7, 5, 6, 31, 8, 27, 5 và 77.

Bạn có thể tạo \(J\) jamcoin khác nhau có độ dài \(N\), cùng chứng minh chúng hợp lệ không?

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test gồm một dòng chứa hai số nguyên \(N,J\).

Dữ liệu ra

Với mỗi bộ test, in \(J+1\) dòng. Dòng đầu chỉ gồm Case #x:, trong đó x là số thứ tự bộ test (bắt đầu từ 1). Mỗi dòng trong \(J\) dòng còn lại gồm một jamcoin độ dài \(N\), theo sau bởi chín số nguyên. Số thứ \(i\) trong chín số đó (đếm từ 1) phải là một ước không tầm thường của jamcoin khi nó được diễn giải trong cơ số \(i+1\).

Mọi jamcoin phải khác nhau. Không được in cùng một jamcoin trên hai dòng khác nhau, kể cả khi dùng bộ ước khác.

Ràng buộc

• \(T=1\) (chỉ có một bộ test).
• Bảo đảm tồn tại ít nhất \(J\) jamcoin khác nhau độ dài \(N\).

Phân nhóm

• Test Set 1 (Hiển thị): \(N=16\), \(J=50\).
• Test Set 2 (Ẩn): \(N=32\), \(J=500\).

Khác thường so với một bài Code Jam, bạn đã biết chính xác nội dung từng tệp đầu vào. Chẳng hạn, tệp đầu vào của Test Set nhỏ luôn gồm đúng hai dòng:

1
16 50

Vì vậy, bạn có thể thực hiện một số tính toán trước khi thực sự tải tệp đầu vào và bắt đầu tính giờ.

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

1
6 3

Case #1:
100011 5 13 147 31 43 1121 73 77 629
111111 21 26 105 1302 217 1032 513 13286 10101
111001 3 88 5 1938 7 208 3 20 11

Nguồn

Google Code Jam 2016, Vòng loại, bài Coin Jam.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.