26 marbles—half yellow and half gray—are distributed between two circles of 13 marbles each. The marbles in each circle can be freely rotated clockwise or counterclockwise. The upper and lower circles are bridged by a smaller circle, which rotates—in the plane of the board—180 degrees, effectively exchanging the three bottommost marbles of the upper circle with the three uppermost marbles of the lower one. The goal is to get all gray marbles to the upper circle and all yellow marbles to the lower one while minimizing the number of times the bridging circle is rotated.

The input is a series of lines, where each line describes an initial board configuration. Each line is a permutation of 13 y’s and 13 g’s. The first half of the line describes the clockwise configuration of the upper circle, and the rest of the line describes the clockwise configuration of the lower one. Of course, each y corresponds to a yellow marble, and each g corresponds to a gray one. The input file will include multiple test cases. Each test case consists of a single line containing some permutation of the string y13g13. All lines (including the last one) are terminated with a newline. The newline immediately follows the last letter on the line.

For each input case, you should print the minimum number of bridge rotations on a single line.

Pacific Northwest 2007