关于符号的说明： 代表字符串 的长度； 代表字符串 下标 处的字符，在本题中，我们从 开始计数； 代表字符串 从下标 开始、到下标 结束的子串（双闭），且有 ； 同 ； 同 。 对于给定的长度为 的字符串 ，我们定义一个最长的字符串 ，满足其既是字符串 的真前缀，又是字符串 的真后缀，且可以为空串，这个字符串的长度 被简记为 。换句话说，使得 、 和 相等的最长字符串长度。 对于字符串 的全部前缀串 分别求解 ，得到 即为 的前缀函数。 你需要构建一个能够维护字符串 的全部前缀函数的数据结构，使得其能支持： 前缀函数查询：输出 的前缀函数，即 。 提示 本题为前缀函数模板题，其实现时间复杂度为 。 特殊测试点信息： 测试点 ，仅使用一个字符构建串。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：此后 行，每行先输入一个整数 ，随后输入一个长度为 、仅由小写字母构成的字符串 代表待查询的字符串。除此之外，保证所有的 之和不超过 。

输出描述:

对于每一组测试数据，在一行上输出 个整数，代表前缀函数 。