시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 112 34 29 34.118%

문제

현수는 조이스틱을 이용해 지렁이를 미로에서 탈출시키는 게임을 하고 있다. 최고 점수를 얻은 경우에는 조이스틱을 이용해서 이름을 입력해야 한다. 이름을 입력하는 과정은 다음과 같다.

가장 처음에 화면에 나와있는 이름은 'A'로만 이루어져 있다. 또, 이름의 첫 글자가 선택되어 있다. 조이스틱을 앞으로 움직이면 선택된 글자가 알파벳 다음 글자로 바뀐다. 조이스틱을 뒤로 움직이면, 알파벳 이전 글자로 바뀐다. 'Z'의 다음 글자는 'A'이고, 'A'의 이전 글자는 'Z'이다.

조이스틱을 왼쪽으로 움직이면, 현재 선택한 글자의 왼쪽 글자를 선택하게 되고, 오른쪽으로 움직이면 오른쪽 글자를 선택하게 된다. 가장 왼쪽 글자가 선택되었을 때, 조이스틱을 왼쪽으로 움직이면 마지막 글자를 선택하게 되고, 마지막 글자를 선택했을 때, 오른쪽으로 움직이면 첫 글자를 선택하게 된다.

현수는 조이스틱을 최소로 움직여서 이름을 입력하려고 한다. 현수가 입력하려고 하는 이름이 주어졌을 때, 이름을 입력하기 위해서 조이스틱을 최소 몇 번 움직여야 하는지 구하는 프로그램을 작성하시오. 현수가 입력하려는 이름의 길이와 처음에 화면에 나타나있는 이름의 길이는 같으며, 마지막에 선택하고 있는 글자는 중요하지 않다.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스의 개수는 최대 100이다.

각 테스트 케이스는 현수가 입력하려고 하는 이름이 주어진다. 이름의 길이는 최대 1000이며, 알파벳 대문자로만 이루어져 있다.

출력

각 테스트 케이스 마다, 조이스틱을 최소 몇 번 움직이면 이름을 입력할 수 있는지 출력한다.

예제 입력 1

2
JEROEN
JAN

예제 출력 1

56
23
W3sicHJvYmxlbV9pZCI6IjM2NjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjZTBcdWI0ZGRcdWM4MTAiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDYwNFx1YzIxOFx1YjI5NCBcdWM4NzBcdWM3NzRcdWMyYTRcdWQyZjFcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0IFx1YzljMFx1YjgwMVx1Yzc3NFx1Yjk3YyBcdWJiZjhcdWI4NWNcdWM1ZDBcdWMxMWMgXHVkMGM4XHVjZDljXHVjMmRjXHVkMGE0XHViMjk0IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NThcdWFjZTAgXHVjNzg4XHViMmU0LiBcdWNkNWNcdWFjZTAgXHVjODEwXHVjMjE4XHViOTdjIFx1YzViYlx1Yzc0MCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjODcwXHVjNzc0XHVjMmE0XHVkMmYxXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWM3NzRcdWI5ODRcdWM3NDQgXHVjNzg1XHViODI1XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViOTg0XHVjNzQ0IFx1Yzc4NVx1YjgyNVx1ZDU1OFx1YjI5NCBcdWFjZmNcdWM4MTVcdWM3NDAgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAwXHVjN2E1IFx1Y2M5OFx1Yzc0Y1x1YzVkMCBcdWQ2NTRcdWJhNzRcdWM1ZDAgXHViMDk4XHVjNjQwXHVjNzg4XHViMjk0IFx1Yzc3NFx1Yjk4NFx1Yzc0MCAmIzM5O0EmIzM5O1x1Yjg1Y1x1YjljYyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWI2MTAsIFx1Yzc3NFx1Yjk4NFx1Yzc1OCBcdWNjYWIgXHVhZTAwXHVjNzkwXHVhYzAwIFx1YzEyMFx1ZDBkZFx1YjQxOFx1YzViNCBcdWM3ODhcdWIyZTQuIFx1Yzg3MFx1Yzc3NFx1YzJhNFx1ZDJmMVx1Yzc0NCBcdWM1NWVcdWM3M2NcdWI4NWMgXHVjNmMwXHVjOWMxXHVjNzc0XHViYTc0IFx1YzEyMFx1ZDBkZFx1YjQxYyBcdWFlMDBcdWM3OTBcdWFjMDAgXHVjNTRjXHVkMzBjXHViY2IzIFx1YjJlNFx1Yzc0YyBcdWFlMDBcdWM3OTBcdWI4NWMgXHViYzE0XHViMDEwXHViMmU0LiBcdWM4NzBcdWM3NzRcdWMyYTRcdWQyZjFcdWM3NDQgXHViNGE0XHViODVjIFx1YzZjMFx1YzljMVx1Yzc3NFx1YmE3NCwgXHVjNTRjXHVkMzBjXHViY2IzIFx1Yzc3NFx1YzgwNCBcdWFlMDBcdWM3OTBcdWI4NWMgXHViYzE0XHViMDEwXHViMmU0LiAmIzM5O1omIzM5O1x1Yzc1OCBcdWIyZTRcdWM3NGMgXHVhZTAwXHVjNzkwXHViMjk0ICYjMzk7QSYjMzk7XHVjNzc0XHVhY2UwLCAmIzM5O0EmIzM5O1x1Yzc1OCBcdWM3NzRcdWM4MDQgXHVhZTAwXHVjNzkwXHViMjk0ICYjMzk7WiYjMzk7XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4NzBcdWM3NzRcdWMyYTRcdWQyZjFcdWM3NDQgXHVjNjdjXHVjYWJkXHVjNzNjXHViODVjIFx1YzZjMFx1YzljMVx1Yzc3NFx1YmE3NCwgXHVkNjA0XHVjN2FjIFx1YzEyMFx1ZDBkZFx1ZDU1YyBcdWFlMDBcdWM3OTBcdWM3NTggXHVjNjdjXHVjYWJkIFx1YWUwMFx1Yzc5MFx1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NThcdWFjOGMgXHViNDE4XHVhY2UwLCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM3M2NcdWI4NWMgXHVjNmMwXHVjOWMxXHVjNzc0XHViYTc0IFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWFlMDBcdWM3OTBcdWI5N2MgXHVjMTIwXHVkMGRkXHVkNTU4XHVhYzhjIFx1YjQxY1x1YjJlNC4gXHVhYzAwXHVjN2E1IFx1YzY3Y1x1Y2FiZCBcdWFlMDBcdWM3OTBcdWFjMDAgXHVjMTIwXHVkMGRkXHViNDE4XHVjNWM4XHVjNzQ0IFx1YjU0YywgXHVjODcwXHVjNzc0XHVjMmE0XHVkMmYxXHVjNzQ0IFx1YzY3Y1x1Y2FiZFx1YzczY1x1Yjg1YyBcdWM2YzBcdWM5YzFcdWM3NzRcdWJhNzQgXHViOWM4XHVjOWMwXHViOWM5IFx1YWUwMFx1Yzc5MFx1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NThcdWFjOGMgXHViNDE4XHVhY2UwLCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVhZTAwXHVjNzkwXHViOTdjIFx1YzEyMFx1ZDBkZFx1ZDU4OFx1Yzc0NCBcdWI1NGMsIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWM2YzBcdWM5YzFcdWM3NzRcdWJhNzQgXHVjY2FiIFx1YWUwMFx1Yzc5MFx1Yjk3YyBcdWMxMjBcdWQwZGRcdWQ1NThcdWFjOGMgXHViNDFjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWQ2MDRcdWMyMThcdWIyOTQgXHVjODcwXHVjNzc0XHVjMmE0XHVkMmYxXHVjNzQ0IFx1Y2Q1Y1x1YzE4Y1x1Yjg1YyBcdWM2YzBcdWM5YzFcdWM1ZWNcdWMxMWMgXHVjNzc0XHViOTg0XHVjNzQ0IFx1Yzc4NVx1YjgyNVx1ZDU1OFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuIFx1ZDYwNFx1YzIxOFx1YWMwMCBcdWM3ODVcdWI4MjVcdWQ1NThcdWI4MjRcdWFjZTAgXHVkNTU4XHViMjk0IFx1Yzc3NFx1Yjk4NFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWM3NzRcdWI5ODRcdWM3NDQgXHVjNzg1XHViODI1XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NFx1YzExYyBcdWM4NzBcdWM3NzRcdWMyYTRcdWQyZjFcdWM3NDQgXHVjZDVjXHVjMThjIFx1YmE4NyBcdWJjODggXHVjNmMwXHVjOWMxXHVjNWVjXHVjNTdjIFx1ZDU1OFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVkNjA0XHVjMjE4XHVhYzAwIFx1Yzc4NVx1YjgyNVx1ZDU1OFx1YjgyNFx1YjI5NCBcdWM3NzRcdWI5ODRcdWM3NTggXHVhZTM4XHVjNzc0XHVjNjQwIFx1Y2M5OFx1Yzc0Y1x1YzVkMCBcdWQ2NTRcdWJhNzRcdWM1ZDAgXHViMDk4XHVkMGMwXHViMDk4XHVjNzg4XHViMjk0IFx1Yzc3NFx1Yjk4NFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWIyOTQgXHVhYzE5XHVjNzNjXHViYTcwLCBcdWI5YzhcdWM5YzBcdWI5YzlcdWM1ZDAgXHVjMTIwXHVkMGRkXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjI5NCBcdWFlMDBcdWM3OTBcdWIyOTQgXHVjOTExXHVjNjk0XHVkNTU4XHVjOWMwIFx1YzU0YVx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMThcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YjI5NCBcdWNkNWNcdWIzMDAgMTAwXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ2MDRcdWMyMThcdWFjMDAgXHVjNzg1XHViODI1XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1OFx1YjI5NCBcdWM3NzRcdWI5ODRcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWM3NzRcdWI5ODRcdWM3NTggXHVhZTM4XHVjNzc0XHViMjk0IFx1Y2Q1Y1x1YjMwMCAxMDAwXHVjNzc0XHViYTcwLCBcdWM1NGNcdWQzMGNcdWJjYjMgXHViMzAwXHViYjM4XHVjNzkwXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTQgXHViOWM4XHViMmU0LCBcdWM4NzBcdWM3NzRcdWMyYTRcdWQyZjFcdWM3NDQgXHVjZDVjXHVjMThjIFx1YmE4NyBcdWJjODggXHVjNmMwXHVjOWMxXHVjNzc0XHViYTc0IFx1Yzc3NFx1Yjk4NFx1Yzc0NCBcdWM3ODVcdWI4MjVcdWQ1NjAgXHVjMjE4IFx1Yzc4OFx1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzY2MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkhpZ2ggU2NvcmUiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSZyc3F1bzt2ZSBqdXN0IGJlZW4gcGxheWluZyBhIHZpZGVvIGdhbWUgaW4gd2hpY2ggeW91IGhhZCB0byBtb3ZlIGEgd29ybSB0aHJvdWdoIGEgbWF6ZSB1c2luZyBhIGpveXN0aWNrLiBZb3UgZ290IHRoZSBoaWdoIHNjb3JlLCBhbmQgbm93IHlvdSBoYXZlIHRvIGVudGVyIHlvdXIgbmFtZSB1c2luZyB0aGlzIGpveXN0aWNrLiBUaGlzIHdvcmtzIGFzIGZvbGxvd3MuPFwvcD5cclxuXHJcbjxwPlRoZSBpbml0aWFsIG5hbWUgZGlzcGxheWVkIG9uIHRoZSBzY3JlZW4gaXMgYSBzdHJpbmcgY29uc2lzdGluZyBvbmx5IG9mICYjMzk7QSYjMzk7IGNoYXJhY3RlcnMuIEluaXRpYWxseSB0aGUgZmlyc3QgbGV0dGVyIG9mIHRoZSBzdHJpbmcgaXMgc2VsZWN0ZWQuIFdoZW4geW91IG1vdmUgdGhlIGpveXN0aWNrIGZvcndhcmQsIHRoZSBzZWxlY3RlZCBsZXR0ZXIgaXMgY2hhbmdlZCB0byB0aGUgbGV0dGVyIHRoYXQgaW1tZWRpYXRlbHkgZm9sbG93cyBpdCBpbiB0aGUgYWxwaGFiZXQuIFdoZW4geW91IG1vdmUgdGhlIGpveXN0aWNrIGJhY2t3YXJkLCB0aGUgc2VsZWN0ZWQgbGV0dGVyIGlzIGNoYW5nZWQgdG8gdGhlIGxldHRlciB0aGF0IGltbWVkaWF0ZWx5IHByZWNlZGVzIGl0IGluIHRoZSBhbHBoYWJldC4gVGhlIGFscGhhYmV0IHdyYXBzIGFyb3VuZCAsIHNvIHRoZSBsZXR0ZXIgZm9sbG93aW5nICYjMzk7WiYjMzk7IGlzICYjMzk7QSYjMzk7IGFuZCB0aGUgbGV0dGVyIHByZWNlZGluZyAmIzM5O0EmIzM5OyBpcyAmIzM5O1omIzM5Oy48XC9wPlxyXG5cclxuPHA+TW92aW5nIHRoZSBqb3lzdGljayBsZWZ0IG9yIHJpZ2h0IGNoYW5nZXMgdGhlIHNlbGVjdGlvbiBvbmUgc3RlcCB0byB0aGUgbGVmdCBvciByaWdodCwgcmVzcGVjdGl2ZWx5LiBUaGUgc2VsZWN0aW9uIGFsc28gd3JhcHMgYXJvdW5kLCBzbyBtb3ZpbmcgbGVmdCB3aGVuIHRoZSBmaXJzdCBsZXR0ZXIgaXMgc2VsZWN0ZWQgd2lsbCBzZWxlY3QgdGhlIGxhc3QgbGV0dGVyIGFuZCB2aWNlIHZlcnNhLjxcL3A+XHJcblxyXG48cD5CZWNhdXNlIHlvdSB3b3VsZCBsaWtlIHRvIHNwZW5kIGFzIGxpdHRsZSB0aW1lIGFzIHBvc3NpYmxlIG9uIGVudGVyaW5nIHlvdXIgbmFtZSwgeW91IHdhbnQgdG8ga25vdyB0aGUgc21hbGxlc3QgcG9zc2libGUgbnVtYmVyIG9mIGpveXN0aWNrIG1vdmVzIG5lZWRlZCB0byBkbyB0aGlzLiBHaXZlbiB0aGUgbmFtZSB5b3Ugd2FudCB0byBlbnRlciwgd3JpdGUgYSBwcm9ncmFtIHRoYXQgY2FsY3VsYXRlcyB0aGUgbWluaW11bSBudW1iZXIgb2YgbW92ZXMgbmVlZGVkLiBZb3UgbWF5IGFzc3VtZSB0aGF0IHRoZSBsZW5ndGggb2YgdGhlIGluaXRpYWwgc3RyaW5nIGlzIHRoZSBzYW1lIGFzIHRoZSBsZW5ndGggb2YgdGhlIG5hbWUgdGhhdCB5b3Ugd2FudCB0byBlbnRlci4gRnVydGhlcm1vcmUsIGl0IGRvZXMgbm90IG1hdHRlciB3aGljaCBsZXR0ZXIgaXMgc2VsZWN0ZWQgYXQgdGhlIGVuZCBvZiB0aGUgcHJvY2Vzcy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBcdWZiMDFyc3QgbGluZSBhIHBvc2l0aXZlIGludGVnZXI6IHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcywgYXQgbW9zdCAxMDAuIEFmdGVyIHRoYXQgcGVyIHRlc3QgY2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5PbmUgbGluZSB3aXRoIGEgc3RyaW5nIHMgKDEgJmxlOyBsZW5ndGgocykgJmxlOyAxIDAwMCkgY29uc2lzdGluZyBvZiB1cHBlcmNhc2UgbGV0dGVyczogdGhlIG5hbWUgdGhhdCB5b3Ugd2FudCB0byBlbnRlci48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPlBlciB0ZXN0IGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+T25lIGxpbmUgd2l0aCBhbiBpbnRlZ2VyOiB0aGUgbWluaW11bSBudW1iZXIgb2Ygam95c3RpY2sgbW92ZXMgbmVlZGVkLjxcL2xpPlxyXG48XC91bD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2010 C번