시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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+XHVhYzAxIFx1YzkwNFx1Yzc1OCBcdWNjOThcdWM3NGMgMTNcdWFjMWMgXHViYjM4XHVjNzkwXHViMjk0IFx1YzcwNFx1Y2FiZCBcdWM2ZDBcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWQ2Y1x1YzJhY1x1Yzc1OCBcdWMwYzlcdWMwYzFcdWM3NDQgXHVjMmRjXHVhY2M0XHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1YjA5OFx1ZDBjMFx1YjBiOCBcdWFjODNcdWM3NzRcdWFjZTAsIFx1YjA5OFx1YmEzOFx1YzljMFx1YjI5NCBcdWM1NDRcdWI3OThcdWNhYmQgXHVjNmQwXHVjNzU4IFx1YzgxNVx1YmNmNFx1Yzc3NFx1YjJlNC4geVx1YjI5NCBcdWIxNzhcdWI3ODBcdWMwYzksIGdcdWIyOTQgXHVkNjhjXHVjMGM5XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YzcwNFx1YzVkMFx1YjI5NCBcdWQ2OGNcdWMwYzkgXHVhZDZjXHVjMmFjLCBcdWM1NDRcdWI3OThcdWM1ZDBcdWIyOTQgXHViMTc4XHViNzgwXHVjMGM5IFx1YWQ2Y1x1YzJhY1x1YjljYyBcdWIxMjNcdWM3NDQgXHViNTRjLCBcdWFjMDBcdWM2YjRcdWIzNzAgXHVjNmQwXHVjNzQ0IFx1YjNjY1x1YjlhY1x1YjI5NCBcdWQ2OGNcdWMyMThcdWM3NTggXHVjZDVjXHVjMTlmXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0NTAzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQnJpZGdlZCBNYXJibGUgUmluZ3MiLCJkZXNjcmlwdGlvbiI6IjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbWJyLnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDozNzRweDsgd2lkdGg6MjAwcHhcIiBcLz4yNiBtYXJibGVzJm1kYXNoO2hhbGYgeWVsbG93IGFuZCBoYWxmIGdyYXkmbWRhc2g7YXJlIGRpc3RyaWJ1dGVkIGJldHdlZW4gdHdvIGNpcmNsZXMgb2YgMTMgbWFyYmxlcyBlYWNoLiBUaGUgbWFyYmxlcyBpbiBlYWNoIGNpcmNsZSBjYW4gYmUgZnJlZWx5IHJvdGF0ZWQgY2xvY2t3aXNlIG9yIGNvdW50ZXJjbG9ja3dpc2UuIFRoZSB1cHBlciBhbmQgbG93ZXIgY2lyY2xlcyBhcmUgYnJpZGdlZCBieSBhIHNtYWxsZXIgY2lyY2xlLCB3aGljaCByb3RhdGVzJm1kYXNoO2luIHRoZSBwbGFuZSBvZiB0aGUgYm9hcmQmbWRhc2g7MTgwIGRlZ3JlZXMsIGVmZmVjdGl2ZWx5IGV4Y2hhbmdpbmcgdGhlIHRocmVlIGJvdHRvbW1vc3QgbWFyYmxlcyBvZiB0aGUgdXBwZXIgY2lyY2xlIHdpdGggdGhlIHRocmVlIHVwcGVybW9zdCBtYXJibGVzIG9mIHRoZSBsb3dlciBvbmUuIFRoZSBnb2FsIGlzIHRvIGdldCBhbGwgZ3JheSBtYXJibGVzIHRvIHRoZSB1cHBlciBjaXJjbGUgYW5kIGFsbCB5ZWxsb3cgbWFyYmxlcyB0byB0aGUgbG93ZXIgb25lIHdoaWxlIG1pbmltaXppbmcgdGhlIG51bWJlciBvZiB0aW1lcyB0aGUgYnJpZGdpbmcgY2lyY2xlIGlzIHJvdGF0ZWQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgaXMgYSBzZXJpZXMgb2YgbGluZXMsIHdoZXJlIGVhY2ggbGluZSBkZXNjcmliZXMgYW4gaW5pdGlhbCBib2FyZCBjb25maWd1cmF0aW9uLiBFYWNoIGxpbmUgaXMgYSBwZXJtdXRhdGlvbiBvZiAxMyB5JnJzcXVvO3MgYW5kIDEzIGcmcnNxdW87cy4gVGhlIGZpcnN0IGhhbGYgb2YgdGhlIGxpbmUgZGVzY3JpYmVzIHRoZSBjbG9ja3dpc2UgY29uZmlndXJhdGlvbiBvZiB0aGUgdXBwZXIgY2lyY2xlLCBhbmQgdGhlIHJlc3Qgb2YgdGhlIGxpbmUgZGVzY3JpYmVzIHRoZSBjbG9ja3dpc2UgY29uZmlndXJhdGlvbiBvZiB0aGUgbG93ZXIgb25lLiBPZiBjb3Vyc2UsIGVhY2ggeSBjb3JyZXNwb25kcyB0byBhIHllbGxvdyBtYXJibGUsIGFuZCBlYWNoIGcgY29ycmVzcG9uZHMgdG8gYSBncmF5IG9uZS4gVGhlIGlucHV0IGZpbGUgd2lsbCBpbmNsdWRlIG11bHRpcGxlIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIGNvbnNpc3RzIG9mIGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyBzb21lIHBlcm11dGF0aW9uIG9mIHRoZSBzdHJpbmcgeTxzdXA+MTM8XC9zdXA+ZzxzdXA+MTM8XC9zdXA+LiBBbGwgbGluZXMgKGluY2x1ZGluZyB0aGUgbGFzdCBvbmUpIGFyZSB0ZXJtaW5hdGVkIHdpdGggYSBuZXdsaW5lLiBUaGUgbmV3bGluZSBpbW1lZGlhdGVseSBmb2xsb3dzIHRoZSBsYXN0IGxldHRlciBvbiB0aGUgbGluZS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBpbnB1dCBjYXNlLCB5b3Ugc2hvdWxkIHByaW50IHRoZSBtaW5pbXVtIG51bWJlciBvZiBicmlkZ2Ugcm90YXRpb25zIG9uIGEgc2luZ2xlIGxpbmUuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d