单点时限: 2.0 sec
内存限制: 512 MB
你最后还是决定饮茶放工，出去和队友吃火锅。不过在此之前火锅店老板已经对评论区进行了一次公关，你已经看不到多少中肯的评价了。同时，你也在评论区发现了一些端倪：因为老板请了水军，评论区的评论呈现出有一些有趣的特点。例如每一条评论的开头都离不开某几句话，因此你用一个小写字母 （a - z） 来表示一种评论。
你还发现评论都是用比较拙劣的自动化工具刷的，因为不仅只有几种评论，依次查看评论甚至发现了 循环节。根据你多年的脚本经验，这个脚本里面有一个长度为 $p$ 的评论列表，这个脚本会按顺序循环往复地发布这 $p$ 条评论。如果我们用字符串 $s = s_1 s_2\dots s_{|s|}$ 表示一系列连续的评论，那么我们说 $p$ 是 $s$ 的循环节，当且仅当：
你现在爬取了评论区所有的 $n$ 条评论，你很好奇老板刷评论的脚本里面的评论列表长什么样。不过，在老板操作以前可能已经存在一些评论了，你不知道老板是从哪一条评论开始用脚本刷评论的，因此你想知道每一个后缀的周期性。具体而言，对于 $i=1 \dots n$，假设最后的 $i$ 条评论是用脚本刷的，你需要求出脚本中所有可能循环节的大小（也即评论列表长度）之和 $a_i$ :
$$ a_i = \sum_{p \text{是} s_{n - i + 1\dots n} \text{的周期}} p .$$
输入包含多组数据。第一行包含一个整数 $T$，代表数据组数。
每组数据的第一行包含一个正整数 $n$ （$1 \le n \le 10^6$），代表评论区评论的数量；第二行包含一个仅包含小写字母的字符串 $s$。
保证所有数据的 $n$ 总和不超过 $10^6$。
对每组数据，在一行内输出 $n$ 个用空格分隔的整数 $a_1,\ a_2,\ \dots,\ a_n$。
3 5 ababa 14 nunhehhehahhhh 8 shanghai
1 2 5 6 11 1 3 6 10 5 11 7 15 24 10 21 12 13 14 1 2 3 4 5 6 7 8
对于第一组数据而言：