Virus synthesis

Viruses are usually bad for your health. So why not fight a virus with another virus? In this problem you work out how to synthesize the helpful kind.

You are given strings over the four letters A, G, T and C. Each string is the DNA nucleotide sequence of a virus you want to synthesize, and only these two operations are allowed.

• Attach one nucleotide to the beginning or the end of the current sequence.
• Replicate the current sequence, reverse the copy, and glue it to the beginning or the end of the original. For example, AGTC becomes AGTCCTGA or CTGAAGTC.

Synthesis starts from the empty sequence. There are many sequences to synthesize and some of them are long, so find a way to build each one in the minimum number of operations.

The first line contains the number of test cases $T$. The test cases follow, one per line.

Each test case consists of a single non-empty string. The string uses only the capital letters A, C, G and T, and its length is at most 100,000.

For each test case, print the minimum total number of operations needed to build the given sequence, one number per line.