문제

ACM-ICPC를 사랑하는 사람이라면 누구나 영혼을 팔 정도로 바라는 것, Accepted다. 약자는 AC. 하지만 현실에서 이를 알아들을 수 있는 사람은 매우 제한적으로, 세상에서는 "koukyoukoukokukikou  (AC 재팬)"의 약자일 뿐이다.

그 사실은 잠시 제쳐두고, 일반적인 키보드의 배열(그림 A-1)을 QWERTY 배열이라 부르는 데 반해 그와는 다른 Dvorak 키보드 배열이 있다. Drvorak 배열에서는 주로 사용되는 자판이 아래쪽에 있기 때문에 훨씬 빠르게 타이핑이 가능하다고 T씨(가명)는 강하게 주장하고 있다. 

(그림 A-1 참조)

이 T씨는 무언가 깨달았다. 바로 "koukyoukoukokukikou"는 Dvorak 배열을 사용하면 한 손으로 타이핑할 수 있다는 것이다. 하지만 동시에 안타까운 사실도 깨달았다. 이 단어는 QWERTY 자판에서도 한 손으로 타이핑할 수 있다는 것이다.

T씨(가명)는 Dvorak 배열을 사용하면 한 손으로 타이핑할 수 있는 또 다른 문자열이 있는지 흥미가 생겼다. 하지만 가능하다면 QWERTY 배열에서는 한 손으로 타이핑할 수 없는 문자열을 찾으려 한다. 이를 위해, 각 문자열에 대해 QWERTY 배열에서 타이핑할 때 사용하는 손이 바뀌는 횟수를 구하는 프로그램을 작성하려 한다. T씨(가명)는 QWERTY 배열을 거의 까먹었다. 대신 프로그램을 작성하자.

QWERTY 배열에서 각 자판을 왼손과 오른손 중 어느 손으로 타이핑해야 하는지 잘 모르겠는 경우, 아래의 그림 A-2를 참조하자.

(그림 A-2 참조)

입력

각 행에 타이핑할 때 손이 바뀌는 횟수를 구해야 하는 문자열이 1개씩 주어진다. 문자열은 알파벳 소문자로만 이루어져 있으면 32글자 이하다. "#"으로만 이루어진 줄이 입력의 종료를 알린다. 이 "#"은 계산해야 할 문자열이 아니다.

출력

입력 각 문자열에 대해 정수 하나를 출력한다. 출력해야 하는 정수는, QWERTY 배열을 사용했을 때 자판을 타이핑하는 손이 바뀌는 횟수이다. 출력에 필요 없는 문자를 덧붙이지 않는다.