Description

病毒通常对健康有害。那么用……其他病毒来对抗它们怎么样？在这个问题中，你需要找出如何合成这样的好病毒。

我们为你准备了一组由字母 $A, G, T$ 和 $C$ 组成的字符串。它们对应于我们想要合成的病毒的 DNA 核苷酸序列，可以使用以下操作：

• 在现有序列的开头或结尾添加一个核苷酸。
• 复制序列，反转复制的片段，并将其粘贴到原序列的开头或结尾（例如，$AGTC$ 可以变成 $AGTCCTGA$ 或 $CTGAAGTC$）。

由于我们有很多这样的序列，其中一些非常长，我们关心效率。找出一种方法，以最少的操作次数合成它们。

Input Format

输入的第一行包含测试用例的数量 $T$。测试用例的描述如下：

每个测试用例由一行组成，包含一个非空字符串。该字符串仅使用大写字母 $A, C, G$ 和 $T$，且长度不超过 $100000$ 个字符。

Output Format

对于每个测试用例，输出一行，包含构建给定序列所需的最小操作总数。

4
AAAA
AGCTTGCA
AAGGGGAAGGGGAA
AAACAGTCCTGACAAAAAAAAAAAAC

3
8
6
18

Hint

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