SETI

외계 문명이 보내는 전파 신호를 해석하려는 연구가 오랫동안 이어져 왔다. 그중에서도 어느 먼 성운에서 오는 신호가 특히 흥미롭다.

각 메시지가 정수 수열 $a_0, a_1, \ldots, a_{n-1}$ 로 전송된다고 가정하면, 올바른 $p$ 를 사용했을 때 다음 함수가 항상 $0 \le f(k) \le 26$ 범위의 값을 가진다는 사실이 밝혀졌다.

$f(k) = \sum_{i=0}^{n-1} a_i k^i \pmod{p}, \quad 1 \le k \le n$

여기서 $n$ 은 메시지의 길이이고, 각 계수는 $0 \le a_i < p$ 를 만족하는 정수이다. $p$ 는 소수로, $n$ 보다 크고 $26$ 보다도 크며, 절대 $30000$ 을 넘지 않는다.

언어학자들은 각 메시지를 영어 알파벳 문자열로 옮겨 적는다. 변환 규칙은 $f(k)$ 가 가질 수 있는 값 $1..26$ 을 각각 문자 a..z 에 대응시키는 것이다 (즉 $1 = a$, $2 = b$, $\ldots$, $26 = z$). 값 $0$ 은 별표 * 로 적는다. $k = 1$ 부터 $n$ 까지 차례로 돌면서 $f(k)$ 에 해당하는 문자를 문자열 끝에 이어 붙인다.

당신의 임무는 이 역변환을 수행하는 프로그램을 작성하는 것이다. 즉, 문자열과 그때 사용된 $p$ 값이 주어지면 대응하는 정수 수열 $a_0, a_1, \ldots, a_{n-1}$ 을 복원해야 한다.

첫 줄에 이어지는 테스트 케이스의 개수를 나타내는 양의 정수 $N$ 이 주어진다. 각 케이스는 한 줄로 이루어지며, 변환에 사용된 $p$ 값과 변환된 문자열이 공백 하나로 구분되어 주어진다. 문자열에 등장할 수 있는 문자는 소문자 a..z 와 별표 * 뿐이며, 길이는 70 을 넘지 않는다.

각 문자열마다 복원된 정수 수열을 한 줄에 출력한다. 정수들은 공백 하나로 구분하며, 첨자 $i$ 가 커지는 순서대로 ($a_0$ 부터 $a_{n-1}$ 까지) 출력한다.