High School Programming League Problems Archive

Everybody has probably heard of Rubik's cube and its uses as a puzzle toy. It has become so famous that every year World championships are organized.

In order to practicing solving Rubik's cube, we need to introduce some notation. Some of it is described here: Rubik's cube notation. 

Only Face Moves are allowed in this task:

•  Clockwise, 90 degrees: F (front face), B (back face), R (right face), L (left face), U (upper face), D (bottom face).
•  Counter clockwise, 90 degrees: F', B', R', L', U', D' .
•  Clockwise, 180 degrees: F2, B2, R2, L2, U2, D2 .
•  Counter clockwise, 180 degrees: F2', B2', R2', L2', U2', D2'.

In our task, the starting position is a solved Rubik's cube configuration, i.e., all cube sides are of the same color. A sequence of commands are given. Your task is to answer how many different colors appear on each of the six sides of the cube after the sequence is completed.

Input

In the first line of standard input you are given an integer T, the number of test cases. T <= 1000.

In the next T lines, a sequence of moves is given. Eight possible characters appear in this sequence: L, R, U, D, F, B, 2 and ' (single quotes). The number of moves will not be greater than 1000.

Output

For each test case write six integers, separated by spaces. These numbers should represent the number of different colors on all six sides of cube in following order: front, right, back, left, up, down. Answer for each test should be printed in a separate line.

Example

Input:
5
RL'
BRL'D'R2DLR'B'R2UB2U'DR2D2'BRL2'D'R2DLR'B'R2UB2U'DR2D2'
R2L2U2D2F2B2
RRRRLLLLUUUUDDDDFFFFBBBB
URU2R'F'F'U'R2URFUF2U'R'

Output:
2 1 2 1 2 2
4 4 5 4 4 4
2 2 2 2 2 2
1 1 1 1 1 1
3 5 5 3 2 3
 

Scoring

By solving this problem you score 10 points.