Problem Description

给定三阶魔方的基本操作：

现给出一个由基本操作组合成的操作序列，求问：对一个初状态（六个面都是拼好的）的魔方进行多少次连续的序列操作后，魔方会恢复到初状态。

Input

第一行为T，表示输入数据组数。

下面T行，每行给出一个合法的操作序列字符串，每行不超过100个字符。

Output

对第i组数据，输出

Case #i:

然后输出一个整数，表示答案。若魔方不会恢复则输出-1。

3
R2
R'R'U2
RU

Case #1:
2
Case #2:
6
Case #3:
105