2922. 三重串

【题目描述】

cyand1317 定义一个串 S 叫做 三重串,当且仅当其同时满足以下性质:

1. |S | > 1。

2. 存在整数 n 使得 |S | = 3n − 2(即 |S | mod 3 = 1)。

3.(设 |S | = 3n − 2)对于任意 1 ≤ i ≤ n 的整数 i,都有 S i = S 2n−i = S 2n+i−2 。

举个例子,abcbabc就是一个三重串,而a(不满足性质 1)

、abccbaabc(不满足性质 2)和aaab(不满足性质 3)都不是。

现在,cyand1317 给出了一个字符串 S ,并让 wangyurzee7 告诉他,这个串有多少

个子串是三重串。

为了帮助对字符串概念一无所知的 wangyurzee7,cyand1317 还对部分概念进行了

说明:

• |S | 表示的是字符串 S 的长度。

• 对于一个满足 1 ≤ i ≤ |S | 的整数 i,S i 表示的是串 S 从左往右数的第 i 个字符。

• 对于整数 i, j,S (i, j) 表示的是 S i , S i+1 , . . . , S j 顺次连接形成的字符串(特别地,

如果 i > j,则 S (i, j) 是空串,但显然,这与这道题并没有任何关系)。对于任意合法的 i, j 得到的 S (i, j),我们把它们叫做 S 的子串。

需要说明的是,在本题中,出现位置不同、但内容相同的子串被认为是不同的子串。

可怜的 wangyurzee7 并不能数清楚眼花缭乱的三重串,所以请你帮帮他。

【输入格式】

从文件 triple.in 中读入数据。

本题包含多组数据。第一行一个非负整数 T 表示数据组数,接下来依次描述每组数

据。对于每组数据:

一行一个只包含小写字母的字符串 S 。

【输出格式】

输出到文件 triple.out 中。

对于每组数据,输出一行一个整数,表示是三重串的子串数目。

【样例输入】

1



ababcbabccbaabc

【样例输出】

2

【提示】

S 的所有子串中,只有 S (1, 4)(abab)和 S (3, 9)(abcbabc)是三重串。

对于100%的数据，|S|<=2*10^5,T组数据的|S|之和不超过10^6。

【来源】