由于评测机性能差异，本题时限相较原题提升了 1 秒。
您有一个由小写英文字母组成的字符串 。您需要对 执行若干次操作，直到它变为空字符串。每次您可以执行以下三种操作中的一种：
一个非空字符串 被称为 的好子串，当且仅当 ， 是 的前缀，且 的反串是 的后缀。长度为 的字符串 的反串是另一个长度为 的字符串 。
求最多能执行多少次第 种操作。
有多组测试数据。第一行输入一个整数 表示测试数据组数。对于每组测试数据：
第一行输入一个由小写字母组成的字符串 （）。
保证所有测试数据 之和不超过 。
每组测试数据输出一行一个整数，表示最多能执行多少次第 种操作。
3 aaaa abbaabba xy
3 4 0
对于第一组样例数据：。
对于第二组样例数据：。
