Virus synthesis

Time limit20sMemory limit256 MB

Summary

Build each DNA string over A, C, G, and T from empty using single-letter attachments or mirrored duplication in the fewest operations.

Level: Hard8 of 10
Topics: Dynamic programming, String matching
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples2

Example 1

Input

4
AAAA
AGCTTGCA
AAGGGGAAGGGGAA
AAACAGTCCTGACAAAAAAAAAAAAC

Expected output

Example 2
Input
```
4
A
C
G
T
```
Expected output
```
1
1
1
1
```