Migrated from Lutece 103 Rubik's Cube

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

The Rubik's Cube is one of the most famous mechanical puzzles in the world. In a classic $3\times 3\times 3$ Rubik's Cube, each of the six faces is covered by nine stickers, among six solid colors (traditionally white, red, blue, orange, green and yellow).

We can name the six faces as F(Front), B(Back), U(Up), D(Down), L(Left), R(Right).

A letter followed by a prime symbol ' means rotating the corresponding face $90$ degrees in counterclockwise direction, while a letter without a prime symbol denotes a clockwise turn. A letter followed by a 2 denotes two turns, in other words, a $180$-degree turn.

One day, Hongshu performed a sequence of moves, which left the puzzle in a scrambled state. After seeing that, Hongshu began to wonder whether repeating the exact same sequence of moves over and over again would bring the cube back to its initial state --- that is, each of the small stickers must return to the exact same place where it started. Could you help him?

Input

One integer $T$ (about $10000$) on the first line indicates the number of cases.

Then followed by $T$ cases, every case contains a single line which is a space-separated list of rotations (no more than $100$ rotations) Hongshu performed.

Output

For each case, print an integer $X$ in a single line, which is the smallest number of rounds Hongshu need to perform all the rotations to bring each sticker to where it was in the beginning(including the first round). If no such $X$ exists, print $-1$ instead.

Samples

2
F2
F B'

2
4

Note

A brute force algorithm may lead to Time Limited Exceed.

Resources

The 8th UESTC Programming Contest Preliminary