Prof. Pang 最近得到了一本精灵语词典，其中包含了许多代表单词的字符串。他认为字符串 $s$ 的一个划分是“美丽的”，如果满足以下两个条件：

• $s = s_1 + s_2 + s_3 + s_4 + s_5 + s_6$，其中 $s_i (1 \le i \le 6)$ 均为非空子串。$a + b$ 表示字符串 $a$ 和 $b$ 的拼接。
• $s_1 = s_2 = s_5$，$s_3 = s_6$。

例如，你可以将字符串 “114514” 划分为 6 部分：“114514” = “1” + “1” + “4” + “5” + “1” + “4”。第一、第二、第五部分相同，第三和第六部分相同。因此，将 $s = \text{“114514”}$ 划分为 $s_1 = \text{“1”}, s_2 = \text{“1”}, s_3 = \text{“4”}, s_4 = \text{“5”}, s_5 = \text{“1”}, s_6 = \text{“4”}$ 是美丽的。

相应地，字符串 $s$ 的“美观度”定义为 $s$ 的美丽划分的数量。

给定一个字符串 $t$，请帮助 Prof. Pang 计算 $t$ 的所有子串的美观度之和。

输入格式

第一行包含一个整数 $T (1 \le T \le 50)$，表示测试用例的数量。 每个测试用例包含一行字符串 $t$，由数字 ‘0’ 到 ‘9’ 组成。 保证每个测试用例中 $t$ 的长度不超过 5000，且所有测试用例的长度总和不超过 30000。

输出格式

对于每个测试用例，输出一行整数，表示 $t$ 的所有子串的美观度之和。

样例

输入 1

2
114514
0000000

输出 1

1
3