Synthesize Good Viruses

Viruses are usually bad for your health. How about fighting them with... other viruses? In this problem, you are given a DNA nucleotide sequence that represents a virus. The sequence consists of the characters A, G, T, and C. You are allowed to build the sequence using the following operations:

• Addition: Add a nucleotide to either the beginning or the end of the current sequence.
• Replication and Reversal: Replicate the entire current sequence, reverse the copy, and glue it to either the beginning or the end of the sequence. For example, if you have AGTC, you can form either AGTCCTGA (appending the reverse) or CTGAAGTC (prepending the reverse).

Your task is to synthesize the given DNA sequence using as few operations as possible. Note that you start with an empty sequence. Since the very first operation cannot be a replication (because there is no sequence to copy), you must begin by adding a single nucleotide. Formally, if you denote the current sequence by \(X\), the allowed operations are:

• \(X \to c+X\) or \(X \to X+c\), where \(c \in \{A,G,T,C\}\).
• \(X \to X+\text{reverse}(X)\) or \(X \to \text{reverse}(X)+X\), provided that \(X\) is non-empty.

For example, the string AGTCCTGA can be seen as coming from AGTC by applying a replication and reversal (since \(AGTCCTGA = AGTC + \text{reverse}(AGTC)\)). If we know that AGTC requires 4 operations, then AGTCCTGA can be synthesized in 5 operations.

inputFormat

The first line contains an integer \(T\) representing the number of test cases. Each of the following \(T\) lines contains a non-empty string \(S\) (with \(1 \leq |S| \leq 100\)) made up of the characters A, G, T, and C. This string corresponds to the DNA sequence of a virus that needs to be synthesized.

outputFormat

For each test case, output a single line containing the minimum number of operations required to synthesize the given DNA sequence.

sample

1
A

1