바이러스 합성

바이러스는 보통 건강에 해롭다. 그렇다면 바이러스를 다른 바이러스로 잡으면 어떨까? 이 문제에서는 그런 이로운 바이러스를 합성하는 방법을 찾는다.

A, G, T, C 네 글자로 이루어진 문자열이 주어진다. 각 문자열은 합성하려는 바이러스의 DNA 염기 서열이고, 합성에는 다음 두 연산만 쓸 수 있다.

• 현재 서열의 앞이나 뒤에 염기 하나를 붙인다.
• 현재 서열을 복제해 뒤집은 다음, 원래 서열의 앞이나 뒤에 이어 붙인다. 예를 들어 AGTC는 AGTCCTGA 또는 CTGAAGTC가 된다.

합성은 빈 서열에서 시작한다. 합성할 서열이 매우 많고 그중에는 아주 긴 것도 있으니, 각 서열을 최소 연산 횟수로 합성하는 방법을 찾아라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 이어서 테스트 케이스가 한 줄에 하나씩 주어진다.

각 테스트 케이스는 빈 문자열이 아닌 문자열 하나로 이루어진다. 문자열은 대문자 A, C, G, T만 쓰고, 길이는 100,000자를 넘지 않는다.

각 테스트 케이스마다 주어진 서열을 만드는 데 필요한 최소 연산 횟수를 한 줄에 하나씩 출력한다.