Description

庞教授最近获得了一本精灵语言的字典，其中包含许多表示他们单词的字符串。他认为字符串 $s$ 的一个划分是美丽的，如果满足以下两个条件：

• $s = s_1 + s_2 + s_3 + s_4 + s_5 + s_6$，其中 $s_i (1\leq i\leq 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=$"114514" 划分为 $s_1=$"1"，$s_2=$"1"，$s_3=$"4"，$s_4=$"5"，$s_5=$"1"，和 $s_6=$"4" 是美丽的。

因此，字符串 $s$ 的美丽定义为 $s$ 的美丽划分的数量。

给定一个字符串 $t$，请帮助庞教授计算 $t$ 的所有子串的美丽之和。

Input Format

第一行包含一个整数 $T~(1\leq T \le 50)$，表示测试用例的数量。

对于每个测试用例，有一行包含字符串 $t$，由数字 '0' 到 '9' 组成。

保证每个测试用例中每个 $t$ 的长度不超过 $5000$，且总长度不超过 $30000$。

Output Format

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

2
114514
0000000

1
3

Hint

题面翻译由 ChatGPT-4o 提供。