SETI

For some years, quite a lot of work has been put into
listening to electromagnetic radio signals received from space,
in order to understand what civilizations in distant galaxies
might be trying to tell us. One signal source that has been of
particular interest to the scientists at *Université de
Technologie Spatiale* is the Nebula Stupidicus.

Recently, it was discovered that if each message is assumed to be transmitted as a sequence of integers $a_0,a_1,...a_{n-1}$, the function $f(k)=(\sum _{i=0}^{n-1}{a_ i k^ i})\bmod {p}$ always evaluates to values $0 \le f(k) \le 26$ for $1 \le k \le n$, provided that the correct value of $p$ is used. $n$ is of course the length of the transmitted message, and the integers $a_ i$ satisfy $0 \le a_ i < p$. $p$ is a prime number that is guaranteed to be larger than $n$ as well as larger than $26$. It is, however, known to never exceed $30\, 000$.

These relationships altogether have been considered too peculiar for being pure coincidences, so this calls for further investigation.

The linguists at the faculty of *Langues et Cultures
Extraterrestres* transcribe these messages to strings in
the English alphabet to make the messages easier to handle
while trying to interpret their meanings. The transcription
procedure simply assigns the letters $a \ldots z$ to the values
$1 \ldots 26$ that
$f(k)$ might evaluate to,
such that $1=a$,
$2=b$ etc. The value
$0$ is transcribed to ‘*’
(an asterisk). While transcribing messages, the linguists
simply loop from $k=1$ to
$n$, and append the
character corresponding to the value of $f(k)$ at the end of the string.

The backward transcription procedure, has however, turned out to be too complex for the linguists to handle by themselves. You are therefore assigned the task of writing a program that converts strings created in this way back to the original number sequence $a_0, \ldots , a_{n-1}$.

On the first line of the input there is a single positive integer $N$, telling the number of test cases to follow. Each case consists of one line containing the value of $p$ to use during the transcription of the string, followed by the actual string to be transcribed. The only allowed characters in the string are the lower case letters ‘a’-‘z’ and ’*’ (asterisk). No string will be longer than 70 characters.

For each transcribed string, output a line with the corresponding list of integers $a_0, \dots , a_{n-1}$, separated by space.

Sample Input 1 | Sample Output 1 |
---|---|

3 31 aaa 37 abc 29 hello*earth |
1 0 0 0 1 0 8 13 9 13 4 27 18 10 12 24 15 |