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

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

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

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

输入格式

输入的第一行包含测试用例的数量 $T$。接下来是各个测试用例的描述： 每个测试用例由一行非空字符串组成。该字符串仅包含大写字母 ‘A’、‘C’、‘G’ 和 ‘T’，且长度不超过 $100\,000$ 个字符。

输出格式

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

样例

输入格式 1

4
AAAA
AGCTTGCA
AAGGGGAAGGGGAA
AAACAGTCCTGACAAAAAAAAAAAAC

输出格式 1

3
8
6
18