Có nhiều loại virus có hại cho sức khỏe của con người (như virus sởi, quai bị, dại,...). Vì thế các nhà khoa học luôn không ngừng bỏ cuộc, tìm cách để tiêu diệt những chủng virus đó. Để có thể hiểu sâu hơn về chúng, họ cần tìm cách để tổng hợp những virus trên.

Ta được cho một xâu gồm các chữ cái A, G, T và C. Dãy kí tự này tương ứng với trình tự nucleotide DNA của virus cần tổng hợp. Ta bắt đầu với một xâu rỗng, và được sử dụng các thao tác sau:

1. Thêm một nucleotide vào đầu hoặc cuối xâu hiện có.
2. Sao chép xâu, đảo ngược đoạn đã sao chép và dán nó vào đầu hoặc cuối xâu ban đầu (ví dụ: AGTC có thể trở thành AGTCCTGA hoặc CTGAAGTC).

Một xâu có thể được tạo từ một chuỗi gồm nhiều thao tác. Tuy nhiên, ta cũng cần phải quan tâm đến hiệu quả. Vì vậy, hãy tìm cách tổng hợp virus sao cho số thao tác được sử dụng là nhỏ nhất.

Input

• Dòng đầu tiên gồm một số nguyên dương ~T (T \leq 100)~, là số lượng bộ dữ liệu.
• ~T~ dòng tiếp theo, mỗi dòng gồm một xâu kí tự ~S_i~ khác rỗng, chi bao gồm các chữ in hoa A, G, T và C.

Output

• Gồm ~T~ dòng, dòng thứ ~i~ gồm một số nguyên dương là số thao tác nhỏ nhất được sử dụng để có thể xây dựng được xâu ~S_i~.

Sample Input

4
AAAA
AGCTTGCA
AAGGGGAAGGGGAA
AAACAGTCCTGACAAAAAAAAAAAAC

Sample Output

3
8
6
18

Giải thích test mẫu:

Cách xây dựng xâu tối ưu cho từng bộ dữ liệu như sau:

1. ~\emptyset~ → A → AA → AAAA.
2. ~\emptyset~ → A → AG → AGC → AGCT → AGCTT → AGCTTG → AGCTTGC → AGCTTGCAA.
3. ~\emptyset~ → A → GA → GGA → AGGGGA → AAGGGGA → AAGGGGAAGGGGAA.
4. ~\emptyset~ → A → AA → AAA → AAAAAA → AAAAAAC → CAAAAAAAAAAAAC rồi thêm những kí tự còn lại vào xâu bằng thao tác ~(1)~.

Scoring