SETI

For years, scientists have listened to radio signals from space, hoping to understand what distant civilizations might be trying to say. One especially interesting source is a faraway nebula.

Researchers found that if each message is transmitted as a sequence of integers $a_0, a_1, \ldots, a_{n-1}$, then, when the correct value of $p$ is used, the function

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

always evaluates to a value in the range $0 \le f(k) \le 26$. Here $n$ is the length of the message, and each coefficient satisfies $0 \le a_i < p$. The number $p$ is a prime that is guaranteed to be larger than both $n$ and $26$, and never exceeds $30000$.

Linguists transcribe each message into a string over the English alphabet. The rule maps the values $1..26$ that $f(k)$ may take to the letters a..z (that is, $1 = a$, $2 = b$, $\ldots$, $26 = z$); the value $0$ is written as an asterisk *. Looping from $k = 1$ to $n$, they append the character corresponding to $f(k)$ to the string.

Your task is to perform the reverse transcription: given the string and the value of $p$ that was used, recover the corresponding integer sequence $a_0, a_1, \ldots, a_{n-1}$.

The first line contains a single positive integer $N$, the number of test cases that follow. Each case is a single line containing the value of $p$ used for the transcription, followed by the string to be transcribed, separated by one space. The only characters allowed in the string are the lowercase letters a..z and the asterisk *, and no string is longer than 70 characters.

For each string, output one line with the recovered list of integers, separated by single spaces, given in ascending order of the index $i$ (from $a_0$ to $a_{n-1}$).