本题没有可用的提交语言。

描述

多年来，人们一直在监听从太空接收到的电磁无线电波信号，以了解遥远星系中的文明可能试图向我们传达什么信息。在宇宙技术大学的科学家们特别关注的一个信号源是“愚蠢星云”。

最近发现，如果假设每条消息是作为整数序列$a_0, a_1, \dots, a_{n-1}$传输的，那么函数$f(k) = \sum_{0 \leq i \leq n-1} a_i k^i \ (\text{mod}\ p)$总是会在$1 \leq k \leq n$时计算出$0 \leq f(k) \leq 26$的值，前提是使用正确的$p$值。$n$当然是传输消息的长度，$a_i$表示满足$0 \leq a_i < p$的整数。$p$是一个质数，它保证大于$n$，也大于26。然而，已知它永远不会超过30000。

这些关系被认为过于奇特，不可能是纯粹的巧合，因此需要进一步调查。

外语学院的语言学家们将这些消息转录为英文字母中的字符串，以便在尝试解释其含义时更容易处理。转录过程简单地将字母a到z分配给$f(k)$可能计算出的值1到26，使得1 = a，2 = b，依此类推。值0被转录为“*”（星号）。在转录消息时，语言学家们简单地从$k = 1$循环到$n$，并将对应于$f(k)$值的字符追加到字符串的末尾。

然而，反向转录过程对于语言学家来说过于复杂，无法自行处理。因此，您被分配了编写一个程序的任务，将一组字符串转换为对应的外星数字序列。

输入

输入的第一行是一个正整数$N$，表示要处理的测试用例数量。每个测试用例由一行组成，包含在转录字符串时使用的$p$值，以及要转录的实际字符串。字符串中只允许出现小写字母“a”到“z”和“*”（星号）。任何字符串的长度都不会超过70个字符。

输出

对于每个转录的字符串，输出一行对应的整数列表，整数之间用空格分隔，每个整数按$i$值的升序排列。

样例输入

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

来源

2004年西北欧