病毒通常对健康有害。那么，用其他病毒来对抗它们呢？在本题中，你需要找出如何合成这些“好”病毒的方法。

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

• 在现有序列的开头或末尾添加一个核苷酸。
• 复制现有序列，将复制的部分反转，并将其连接到原序列的开头或末尾（例如，AGTC 可以变为 AGTCCTGA 或 CTGAAGTC）。

我们非常关注效率，因为我们有许多这样的序列，其中一些非常长。请找到一种以最少操作次数合成它们的方法。

输入格式

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

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

输出格式

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

样例

输入 1

4
AAAA
AGCTTGCA
AAGGGGAAGGGGAA
AAACAGTCCTGACAAAAAAAAAAAAC

输出 1

3
8
6
18