시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 5 3 3 60.000%

문제

구슬 26개(회색 13개, 노란색 13개)가 오른쪽 그림과 같이 두 원에 놓여있다. 각각의 원에 있는 구슬은 시계방향이나 반시계방향으로 자유롭게 돌릴 수 있다.

위쪽 원과 아래쪽 원은 작은 원으로 연결되어 있다. 이 원은 항상 180도씩 돌릴 수 있으며, 위쪽 구슬 3개와 아럐쪽 구슬 3개의 위치를 서로 바꾼다.

상근이는 위에는 회색 구슬, 아래에는 노란색 구슬만 있게 만들고한다. 이때, 가운데 원을 돌리는 회수의 최솟값을 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, 각 원에 있는 조약돌의 색상이 주어진다. 모든 줄은 y 13개와 g 13개의 순열이다. 

각 줄의 처음 13개 문자는 위쪽 원에 있는 구슬의 색상을 시계방향으로 나타낸 것이고, 나머지는 아래쪽 원의 정보이다. y는 노란색, g는 회색을 나타낸다.

출력

각 테스트 케이스에 대해서, 위에는 회색 구슬, 아래에는 노란색 구슬만 넣을 때, 가운데 원을 돌리는 회수의 최솟값을 출력한다.

예제 입력 1

gggggggggggggyyyyyyyyyyyyy
yyyyyggggggggyyyygggggyyyy
gyyygyggyyygyyggyyggggyygg
ygygygygygygygygygygygygyg

예제 출력 1

0
2
5
6
W3sicHJvYmxlbV9pZCI6IjQ1MDMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFkNmNcdWMyYWMiLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbWJyLnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDozNzRweDsgd2lkdGg6MjAwcHhcIiBcLz5cdWFkNmNcdWMyYWMgMjZcdWFjMWMoXHVkNjhjXHVjMGM5IDEzXHVhYzFjLCBcdWIxNzhcdWI3ODBcdWMwYzkgMTNcdWFjMWMpXHVhYzAwIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWFkZjhcdWI5YmNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YjQ1MCBcdWM2ZDBcdWM1ZDAgXHViMTkzXHVjNWVjXHVjNzg4XHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHVjNmQwXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWFkNmNcdWMyYWNcdWM3NDAgXHVjMmRjXHVhY2M0XHViYzI5XHVkNWE1XHVjNzc0XHViMDk4IFx1YmMxOFx1YzJkY1x1YWNjNFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWM3OTBcdWM3MjBcdWI4NmRcdWFjOGMgXHViM2NjXHViOWI0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcblxyXG5cclxuPHA+XHVjNzA0XHVjYWJkIFx1YzZkMFx1YWNmYyBcdWM1NDRcdWI3OThcdWNhYmQgXHVjNmQwXHVjNzQwIFx1Yzc5MVx1Yzc0MCBcdWM2ZDBcdWM3M2NcdWI4NWMgXHVjNWYwXHVhY2IwXHViNDE4XHVjNWI0IFx1Yzc4OFx1YjJlNC4gXHVjNzc0IFx1YzZkMFx1Yzc0MCBcdWQ1NmRcdWMwYzEgMTgwXHViM2M0XHVjNTI5IFx1YjNjY1x1YjliNCBcdWMyMTggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWM3MDRcdWNhYmQgXHVhZDZjXHVjMmFjIDNcdWFjMWNcdWM2NDAgXHVjNTQ0XHViN2QwXHVjYWJkIFx1YWQ2Y1x1YzJhYyAzXHVhYzFjXHVjNzU4IFx1YzcwNFx1Y2U1OFx1Yjk3YyBcdWMxMWNcdWI4NWMgXHViYzE0XHVhZmJjXHViMmU0LjxcL3A+XHJcblxyXG5cclxuXHJcbjxwPlx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWM3MDRcdWM1ZDBcdWIyOTQgXHVkNjhjXHVjMGM5IFx1YWQ2Y1x1YzJhYywgXHVjNTQ0XHViNzk4XHVjNWQwXHViMjk0IFx1YjE3OFx1Yjc4MFx1YzBjOSBcdWFkNmNcdWMyYWNcdWI5Y2MgXHVjNzg4XHVhYzhjIFx1YjljY1x1YjRlNFx1YWNlMFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViNTRjLCBcdWFjMDBcdWM2YjRcdWIzNzAgXHVjNmQwXHVjNzQ0IFx1YjNjY1x1YjlhY1x1YjI5NCBcdWQ2OGNcdWMyMThcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIFx1YWMwMSBcdWM2ZDBcdWM1ZDAgXHVjNzg4XHViMjk0IFx1Yzg3MFx1YzU3ZFx1YjNjY1x1Yzc1OCBcdWMwYzlcdWMwYzFcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWJhYThcdWI0ZTAgXHVjOTA0XHVjNzQwIHkgMTNcdWFjMWNcdWM2NDAgZyAxM1x1YWMxY1x1Yzc1OCBcdWMyMWNcdWM1ZjRcdWM3NzRcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcblxyXG5cclxuPHA+XHVhYzAxIFx1YzkwNFx1Yzc1OCBcdWNjOThcdWM3NGMgMTNcdWFjMWMgXHViYjM4XHVjNzkwXHViMjk0IFx1YzcwNFx1Y2FiZCBcdWM2ZDBcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWQ2Y1x1YzJhY1x1Yzc1OCBcdWMwYzlcdWMwYzFcdWM3NDQgXHVjMmRjXHVhY2M0XHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiOCBcdWFjODNcdWM3NzRcdWFjZTAsIFx1YjA5OFx1YmEzOFx1YzljMFx1YjI5NCBcdWM1NDRcdWI3OThcdWNhYmQgXHVjNmQwXHVjNzU4IFx1YzgxNVx1YmNmNFx1Yzc3NFx1YjJlNC4geVx1YjI5NCBcdWIxNzhcdWI3ODBcdWMwYzksIGdcdWIyOTQgXHVkNjhjXHVjMGM5XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YzcwNFx1YzVkMFx1YjI5NCBcdWQ2OGNcdWMwYzkgXHVhZDZjXHVjMmFjLCBcdWM1NDRcdWI3OThcdWM1ZDBcdWIyOTQgXHViMTc4XHViNzgwXHVjMGM5IFx1YWQ2Y1x1YzJhY1x1YjljYyBcdWIxMjNcdWM3NDQgXHViNTRjLCBcdWFjMDBcdWM2YjRcdWIzNzAgXHVjNmQwXHVjNzQ0IFx1YjNjY1x1YjlhY1x1YjI5NCBcdWQ2OGNcdWMyMThcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0NTAzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQnJpZGdlZCBNYXJibGUgUmluZ3MgIiwiZGVzY3JpcHRpb24iOiI8cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL21ici5wbmdcIiBzdHlsZT1cImZsb2F0OnJpZ2h0OyBoZWlnaHQ6Mzc0cHg7IHdpZHRoOjIwMHB4XCIgXC8+MjYgbWFyYmxlcyZtZGFzaDtoYWxmIHllbGxvdyBhbmQgaGFsZiBncmF5Jm1kYXNoO2FyZSBkaXN0cmlidXRlZCBiZXR3ZWVuIHR3byBjaXJjbGVzIG9mIDEzIG1hcmJsZXMgZWFjaC4gVGhlIG1hcmJsZXMgaW4gZWFjaCBjaXJjbGUgY2FuIGJlIGZyZWVseSByb3RhdGVkIGNsb2Nrd2lzZSBvciBjb3VudGVyY2xvY2t3aXNlLiBUaGUgdXBwZXIgYW5kIGxvd2VyIGNpcmNsZXMgYXJlIGJyaWRnZWQgYnkgYSBzbWFsbGVyIGNpcmNsZSwgd2hpY2ggcm90YXRlcyZtZGFzaDtpbiB0aGUgcGxhbmUgb2YgdGhlIGJvYXJkJm1kYXNoOzE4MCBkZWdyZWVzLCBlZmZlY3RpdmVseSBleGNoYW5naW5nIHRoZSB0aHJlZSBib3R0b21tb3N0IG1hcmJsZXMgb2YgdGhlIHVwcGVyIGNpcmNsZSB3aXRoIHRoZSB0aHJlZSB1cHBlcm1vc3QgbWFyYmxlcyBvZiB0aGUgbG93ZXIgb25lLiBUaGUgZ29hbCBpcyB0byBnZXQgYWxsIGdyYXkgbWFyYmxlcyB0byB0aGUgdXBwZXIgY2lyY2xlIGFuZCBhbGwgeWVsbG93IG1hcmJsZXMgdG8gdGhlIGxvd2VyIG9uZSB3aGlsZSBtaW5pbWl6aW5nIHRoZSBudW1iZXIgb2YgdGltZXMgdGhlIGJyaWRnaW5nIGNpcmNsZSBpcyByb3RhdGVkLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGlzIGEgc2VyaWVzIG9mIGxpbmVzLCB3aGVyZSBlYWNoIGxpbmUgZGVzY3JpYmVzIGFuIGluaXRpYWwgYm9hcmQgY29uZmlndXJhdGlvbi4gRWFjaCBsaW5lIGlzIGEgcGVybXV0YXRpb24gb2YgMTMgeSZyc3F1bztzIGFuZCAxMyBnJnJzcXVvO3MuIFRoZSBmaXJzdCBoYWxmIG9mIHRoZSBsaW5lIGRlc2NyaWJlcyB0aGUgY2xvY2t3aXNlIGNvbmZpZ3VyYXRpb24gb2YgdGhlIHVwcGVyIGNpcmNsZSwgYW5kIHRoZSByZXN0IG9mIHRoZSBsaW5lIGRlc2NyaWJlcyB0aGUgY2xvY2t3aXNlIGNvbmZpZ3VyYXRpb24gb2YgdGhlIGxvd2VyIG9uZS4gT2YgY291cnNlLCBlYWNoIHkgY29ycmVzcG9uZHMgdG8gYSB5ZWxsb3cgbWFyYmxlLCBhbmQgZWFjaCBnIGNvcnJlc3BvbmRzIHRvIGEgZ3JheSBvbmUuIFRoZSBpbnB1dCBmaWxlIHdpbGwgaW5jbHVkZSBtdWx0aXBsZSB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBjb25zaXN0cyBvZiBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgc29tZSBwZXJtdXRhdGlvbiBvZiB0aGUgc3RyaW5nIHk8c3VwPjEzPFwvc3VwPmc8c3VwPjEzPFwvc3VwPi4gQWxsIGxpbmVzIChpbmNsdWRpbmcgdGhlIGxhc3Qgb25lKSBhcmUgdGVybWluYXRlZCB3aXRoIGEgbmV3bGluZS4gVGhlIG5ld2xpbmUgaW1tZWRpYXRlbHkgZm9sbG93cyB0aGUgbGFzdCBsZXR0ZXIgb24gdGhlIGxpbmUuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggaW5wdXQgY2FzZSwgeW91IHNob3VsZCBwcmludCB0aGUgbWluaW11bSBudW1iZXIgb2YgYnJpZGdlIHJvdGF0aW9ucyBvbiBhIHNpbmdsZSBsaW5lLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==