QWERTY 자판

Albert는 QWERTY 키보드(위 그림 참고)를 이용해 영문 대문자 ('A'-'Z')로 구성된 문자열을 입력하려 한다. 아직 키보드를 다루는 데 서툰 Albert는 왼쪽 검지만으로 버튼을 누르는 버릇이 있다.

버튼 하나를 눌렀다 떼어 글자 하나를 입력하는 데 1초가 걸리고, 검지를 한 버튼에서 인접한 다른 버튼으로 옮기는 데 2초가 걸린다. 문자열을 입력하는 동안 손가락은 항상 키보드 버튼 위에서만 움직인다.

각 버튼 주위에는 최대 6개의 인접한 버튼이 있다. 예를 들어 검지를 S버튼에서 A, W, E, D, X, Z 중 하나로 옮기는 데 2초가 걸린다.

Albert가 어떤 문자열을 입력하려면 먼저 왼쪽 검지를 그 문자열의 첫 글자에 해당하는 버튼 위에 올려놓고, 그때부터 시간을 잰다.

"QWERTY"라는 문자열을 입력하려면 다음과 같이 16초 만에 입력할 수 있다.

• 입력하기 전에 왼쪽 검지를 Q버튼 위로 옮긴다. 이때 걸리는 시간은 세지 않는다.
• Q버튼을 눌렀다 떼어 입력하는 데 1초가 걸린다. (총 1초)
• W버튼으로 이동하는 데 2초가 걸린다. (총 3초)
• W버튼을 눌렀다 떼어 입력하는 데 1초가 걸린다. (총 4초)
• E버튼으로 이동하는 데 2초가 걸린다. (총 6초)
• E버튼을 눌렀다 떼어 입력하는 데 1초가 걸린다. (총 7초)
• R버튼으로 이동하는 데 2초가 걸린다. (총 9초)
• R버튼을 눌렀다 떼어 입력하는 데 1초가 걸린다. (총 10초)
• T버튼으로 이동하는 데 2초가 걸린다. (총 12초)
• T버튼을 눌렀다 떼어 입력하는 데 1초가 걸린다. (총 13초)
• Y버튼으로 이동하는 데 2초가 걸린다. (총 15초)
• Y버튼을 눌렀다 떼어 입력하는 데 1초가 걸린다. (총 16초)

다른 예로, "LOM"이라는 문자열을 입력하려면 9초가 걸린다.

• L버튼을 눌렀다 떼어 입력하는 데 1초가 걸린다. (총 1초)
• O버튼으로 이동하는 데 2초가 걸린다. (총 3초)
• O버튼을 눌렀다 떼어 입력하는 데 1초가 걸린다. (총 4초)
• M버튼으로 이동하는 데 4초가 걸린다. (O -> K -> M으로 이동하는 것이 가장 빠르다.) (총 8초)
• M버튼을 눌렀다 떼어 입력하는 데 1초가 걸린다. (총 9초)

영문 대문자 ('A'-'Z')로만 구성된 문자열이 주어졌을 때, Albert가 가장 빠르게 입력할 경우 몇 초가 필요한지 계산하는 프로그램을 작성하시오.

첫 줄에 테스트 케이스의 수 T가 주어진다.

각 테스트 케이스는 한 줄에 걸쳐 영문 대문자로만 구성된 문자열이 공백 없이 주어진다.

각 테스트 케이스마다 주어진 문자열을 입력하는 데 걸리는 최소 시간을 출력한다.

• 1 ≤ T ≤ 10
• 2 ≤ 문자열의 길이 ≤ 100
• 각 문자열은 영문 대문자 ('A'-'Z')만을 포함한다.