암호화된 팬그램

Code Jam 팀에서는 영어 알파벳의 각 글자를 적어도 한 번씩 사용하는 구절인 팬그램을 서로 보내는 것을 즐긴다. 팬그램의 흔한 예로 "재빠른 갈색 여우가 게으른 개를 뛰어넘는다"가 있다. 때때로 팬그램에는 기밀 정보가 들어 있다. 예를 들면 CJ QUIZ: KNOW BEVY OF DP FLUX ALGORITHMS이다. 따라서 이를 안전하게 보호해야 한다.

몇 분 동안 암호학 교과서를 살펴본 결과, 두 큰 소수의 곱을 소인수분해하는 것은 매우 어렵다는 사실을 알게 되었고, 이를 바탕으로 암호화 방식을 고안했다. 먼저 다음과 같이 준비했다.

• 어떤 정수 N보다 큰 수가 하나도 없도록 서로 다른 소수 26개를 선택했다.

• 그 소수들을 오름차순으로 정렬했다. 그런 다음 가장 작은 소수를 글자 A에, 두 번째로 작은 소수를 글자 B에 배정하는 식으로 계속했다.

• 팀원 모두가 이 목록을 외웠다.

이제 팬그램을 메시지로 보내려 할 때마다 먼저 모든 공백을 제거하여 평문 메시지를 만든다. 그런 다음 평문의 첫 번째 글자에 해당하는 소수와 두 번째 글자에 해당하는 소수의 곱을 적는다. 이어서 평문의 두 번째 글자와 세 번째 글자에 해당하는 소수의 곱을 적는 식으로 계속하여, 끝에서 두 번째 글자와 마지막 글자에 해당하는 소수의 곱까지 적는다. 이렇게 새로 만든 값의 목록이 암호문이다. 값의 개수는 평문 메시지의 문자 수보다 하나 적다.

예를 들어 N = 103이고, 짝수는 소인수분해하기가 너무 쉽다고 우려하여 처음 26개의 홀수 소수를 사용하기로 했다고 하자. 그러면 A = 3, B = 5, C = 7, D = 11이고, 이런 식으로 계속하여 Z = 103까지 배정된다. 또한 위의 CJ QUIZ... 팬그램을 암호화하려 하므로 평문이 CJQUIZKNOWBEVYOFDPFLUXALGORITHMS이라고 하자. 그러면 암호문의 첫 번째 값은 C에 해당하는 소수인 7와 J에 해당하는 소수인 31의 곱인 217이다. 다음 값은 1891이고, 이런 식으로 계속하여 마지막 값은 3053이다.

암호문 메시지와 사용한 N의 값을 제공한다. 어떤 소수를 사용했는지 또는 암호문을 어떻게 복호화하는지는 알려 주지 않는다. 그래도 평문을 복원할 수 있겠는가?

제한

1 ≤ T ≤ 100. 테스트 세트별 시간 제한: 20초. 메모리 제한: 1 GB. 25 ≤ L ≤ 100. 평문에는 영어 알파벳의 각 글자가 적어도 한 번씩 포함된다.

테스트 세트 1 (공개)

101 ≤ N ≤ 10000.

테스트 세트 2 (비공개)

101 ≤ N ≤ $10^{100}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어지며, 각 테스트 케이스는 두 줄로 구성된다. 첫 번째 줄에는 위에서 설명한 N과 암호문의 값 목록 길이 L, 두 정수가 주어진다. 두 번째 줄에는 암호문의 값 목록을 이루는 L개의 정수가 주어진다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x은 테스트 케이스 번호이며(1부터 시작), y은 L + 1개의 영어 알파벳 대문자로 이루어진 문자열인 평문이다.