Rubik Cycle

Almost everyone knows the Rubik's Cube, a 3-D puzzle whose six faces are each covered with nine stickers. The stickers come in six colors: blue, yellow, orange, white, green, and red. In the starting state the nine stickers on a face all have the same color. A mechanism inside the cube turns each face on its own, which mixes the sticker colors across the faces.

The six faces are written F, B, U, D, L, and R, as in the figure below. F is the front face, B is the back face, U is the top face, D is the bottom face, L is the left face, and R is the right face.

Turning one face is called a move. A move is written with the letter of its face.

• An uppercase letter turns that face 90 degrees clockwise.
• A lowercase letter turns that face 90 degrees counter-clockwise.

The direction is measured by someone looking straight at that face from outside the cube. For example, F turns face F 90 degrees clockwise, and r turns face R 90 degrees counter-clockwise. A string of these letters is a sequence of moves, applied from left to right. So rDF turns face R 90 degrees counter-clockwise, then face D 90 degrees clockwise, then face F 90 degrees clockwise.

The Rubik's Cube has this property: any sequence of moves, applied over and over, brings the cube back to the state it had before the first application. For example, the cube returns to that state after four applications of the sequence B.

Given a sequence of moves, write a program that finds the smallest number of complete applications of the sequence that brings the cube back to its starting state.

The input holds several test cases. Each test case is one line holding a single sequence of moves. The input ends at end of file.

Constraints

• Each sequence holds at least 1 and at most 80 moves.
• Each sequence uses only the twelve letters F, B, U, D, L, R, f, b, u, d, l, r.

For each test case print one line holding a single integer, the smallest number of complete applications of the sequence that brings the cube back to its starting state.