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')만을 포함한다.