本题转译自 [NOI2014] 动物园。 给定一个长度为 的字符串 ，下标从 开始。 我们定义数组 中的第 个元素 为第 个前缀 中满足以下条件的非空子串数量： 既是 的前缀，也是 的后缀； 该前缀与后缀不重叠（即两部分在下标意义上没有公共字符）。 现在，请你计算如下表达式，由于答案可能很大，请将答案对 取模后输出： 【名词解释】 字符串的前缀：从字符串的第一个字符开始，向后连续取若干个字符得到的字符串。更具体地，字符串 前 个字符构成的字符串被称为 的第 个前缀，也记为 。 子串：从原字符串中，连续的选择一段字符（可以全选、可以不选）得到的新字符串。 字符串的后缀：从字符串的最后一个字符开始，向前连续取若干个字符得到的字符串。更具体地，字符串 后 个字符构成的字符串被称为 的第 个后缀，也记为 。

输入描述:

每个测试文件均包含多组测试数据。第一行输入一个整数 代表数据组数，每组测试数据描述如下：在一行上输入一个长度为 ，仅由小写英文字母组成的字符串 。

输出描述:

对于每一组测试数据，新起一行输出一个整数，表示所求表达式的值对 取模后的结果。