HZNUOJ

SETI

Tags:   高斯消元
Time Limit:  1 s      Memory Limit:   64 MB
Submission:4     AC:2     Score:99.87

Input

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.

Output

For each transcribed string, output a line with the corresponding list of integers, separated by space, with each integer given in the order of ascending values of i.

Samples

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