Trong đội Code Jam, chúng tôi thích gửi cho nhau các pangram: những cụm từ dùng mỗi chữ cái trong bảng chữ cái tiếng Anh ít nhất một lần. Một ví dụ quen thuộc là “the quick brown fox jumps over the lazy dog”. Đôi khi pangram chứa thông tin mật — chẳng hạn CJ QUIZ: KNOW BEVY OF DP FLUX ALGORITHMS — nên chúng tôi cần giữ chúng an toàn.

Sau vài phút đọc sách mật mã học, chúng tôi biết rằng việc phân tích tích của hai số nguyên tố lớn là rất khó, nên đã thiết kế một hệ mã dựa trên điều đó. Trước tiên, chúng tôi chuẩn bị như sau:

• Chọn 26 số nguyên tố khác nhau, không số nào lớn hơn số nguyên \(N\).
• Sắp xếp các số nguyên tố theo thứ tự tăng dần; gán số nhỏ nhất cho chữ A, số nhỏ thứ hai cho B, và cứ thế.
• Mọi thành viên trong đội ghi nhớ danh sách này.

Khi muốn gửi một pangram, trước hết chúng tôi xóa mọi khoảng trắng để tạo bản rõ. Sau đó, viết tích của số nguyên tố ứng với ký tự thứ nhất và số ứng với ký tự thứ hai; tiếp theo là tích ứng với ký tự thứ hai và thứ ba; cứ thế cho tới tích ứng với hai ký tự cuối. Danh sách mới là bản mã, có ít hơn bản rõ đúng một phần tử.

Ví dụ, giả sử \(N=103\) và ta chọn 26 số nguyên tố lẻ đầu tiên vì lo rằng số chẵn quá dễ phân tích. Khi đó A \(=3\), B \(=5\), C \(=7\), D \(=11\), ..., Z \(=103\). Nếu mã hóa pangram CJ QUIZ... ở trên thì bản rõ là CJQUIZKNOWBEVYOFDPFLUXALGORITHMS. Giá trị đầu của bản mã là \(7\) (số nguyên tố của C) nhân \(31\) (số của J), bằng \(217\); giá trị kế tiếp là \(1891\), và cứ thế, kết thúc bằng \(3053\).

Bạn được cung cấp bản mã và giá trị \(N\) đã dùng, nhưng không được biết các số nguyên tố đã chọn hay cách giải mã. Hãy khôi phục bản rõ.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test gồm hai dòng. Dòng đầu chứa hai số nguyên \(N\) như mô tả ở trên và \(L\), độ dài danh sách bản mã. Dòng thứ hai chứa \(L\) số nguyên của bản mã.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y là chuỗi gồm \(L+1\) chữ cái tiếng Anh viết hoa: bản rõ.

Ràng buộc

• \(1\le T\le100\).
• \(25\le L\le100\).
• Bản rõ chứa mỗi chữ cái tiếng Anh ít nhất một lần.

Phân nhóm

Test Set 1 (Visible): \(101\le N\le10000\).

Test Set 2 (Hidden): \(101\le N\le10^{100}\).

Đ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ụ

2
103 31
217 1891 4819 2291 2987 3811 1739 2491 4717 445 65 1079 8383 5353 901 187 649 1003 697 3239 7663 291 123 779 1007 3551 1943 2117 1679 989 3053
10000 25
3292937 175597 18779 50429 375469 1651121 2102 3722 2376497 611683 489059 2328901 3150061 829981 421301 76409 38477 291931 730241 959821 1664197 3057407 4267589 4729181 5335543

Case #1: CJQUIZKNOWBEVYOFDPFLUXALGORITHMS
Case #2: SUBDERMATOGLYPHICFJKNQVWXZ

Nguồn

Google Code Jam 2019, Vòng loại, bài Cryptopangrams.

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