#513. 三阶魔方

三阶魔方

题目背景

灰太狼学长最近正在备战考研。一次刷题间隙,他本想随手转几下三阶魔方放松一下,却无意间迷上了研究魔方公式。

他发现:从还原状态出发,不断重复执行同一套公式,魔方最终总会回到最初的状态。例如,公式 U 连续执行 44 次后会恢复原状;公式 UU 连续执行 22 次后就会恢复原状。

为了弄清一套公式究竟会占用多少个“复习间隙”,灰太狼学长想请你计算:至少完整执行多少遍给定公式,魔方才会第一次恢复原状?

问题描述

一颗三阶魔方的表面共有 6×9=546\times 9=54 个色块位置,编号为 00 到 5353。为了精确记录魔方状态,我们也给这 5454 个色块分别编号 00 到 5353。开始时,第 ii 号色块位于第 ii 号位置;只有当每个编号色块都回到自己的初始位置时,才称魔方恢复原状。

给定一个仅由 U、D、L、R、F、B 组成的非空字符串 SS。字符串中的每个字符表示:从魔方外侧正对相应面观察时,将该面所在的一层顺时针旋转 90∘90^\circ。

六种操作分别表示:

操作 含义
U 上面所在的一层顺时针旋转 90∘90^\circ
D 下面所在的一层顺时针旋转 90∘90^\circ
L 左面所在的一层顺时针旋转 90∘90^\circ
R 右面所在的一层顺时针旋转 90∘90^\circ
F 前面所在的一层顺时针旋转 90∘90^\circ
B 后面所在的一层顺时针旋转 90∘90^\circ

魔方色块位置的展开图如下。每个面的编号均按照图中方向排列:

                         +----------+
                         |  0  1  2 |
                         |  3  4  5 |  U
                         |  6  7  8 |
                         +----------+
+----------+-------------+----------+-------------+
| 18 19 20 | 36 37 38    | 27 28 29 | 45 46 47    |
| 21 22 23 | 39 40 41    | 30 31 32 | 48 49 50    |
| 24 25 26 | 42 43 44    | 33 34 35 | 51 52 53    |
|     L    |      F      |     R    |      B      |
+----------+-------------+----------+-------------+
                         +----------+
                         |  9 10 11 |
                         | 12 13 14 |  D
                         | 15 16 17 |
                         +----------+

为使旋转规则完全明确,下表给出了六种操作对应的置换环。记号 (a b c d)(a\ b\ c\ d) 表示一次操作后:位置 aa 上的色块移动到位置 bb,位置 bb 上的色块移动到位置 cc,位置 cc 上的色块移动到位置 dd,位置 dd 上的色块移动到位置 aa。同一行中的所有置换环同时发生,未列出的位置保持不变。

操作 置换环
U $(0\ 2\ 8\ 6)(1\ 5\ 7\ 3)(18\ 45\ 27\ 36)(19\ 46\ 28\ 37)(20\ 47\ 29\ 38)$
D $(9\ 11\ 17\ 15)(10\ 14\ 16\ 12)(24\ 42\ 33\ 51)(25\ 43\ 34\ 52)(26\ 44\ 35\ 53)$
L $(0\ 36\ 9\ 53)(3\ 39\ 12\ 50)(6\ 42\ 15\ 47)(18\ 20\ 26\ 24)(19\ 23\ 25\ 21)$
R $(2\ 51\ 11\ 38)(5\ 48\ 14\ 41)(8\ 45\ 17\ 44)(27\ 29\ 35\ 33)(28\ 32\ 34\ 30)$
F $(6\ 27\ 11\ 26)(7\ 30\ 10\ 23)(8\ 33\ 9\ 20)(36\ 38\ 44\ 42)(37\ 41\ 43\ 39)$
B $(0\ 24\ 17\ 29)(1\ 21\ 16\ 32)(2\ 18\ 15\ 35)(45\ 47\ 53\ 51)(46\ 50\ 52\ 48)$

每一遍都必须从头到尾完整执行一次字符串 SS。请求出最小正整数 kk,使得连续执行 kk 遍 SS 后,每个色块都回到初始位置。

你需要独立回答 TT 组询问。每组询问开始时,魔方都会重新处于初始状态。

输入格式

第一行包含一个整数 TT,表示询问数量。

接下来 TT 行,每行包含一个非空字符串 SS,表示一套魔方公式。

输出格式

对于每组询问,输出一行一个整数,表示魔方第一次恢复原状时,公式 SS 需要被完整执行的遍数。

数据范围

1≤T≤2×1041\le T\le 2\times 10^4。

1≤∣S∣1\le |S|,且所有询问的字符串长度之和不超过 2×1052\times 10^5。

SS 仅由大写字母 U、D、L、R、F、B 组成。

样例

输入数据 1

3
U
UU
UUUU

输出数据 1

4
2
1

样例解释

  • 对于 U,同一层需要旋转 44 次才能回到原位。
  • 对于 UU,完整执行一遍相当于旋转 180∘180^\circ,因此执行 22 遍后恢复原状。
  • 对于 UUUU,完整执行一遍后魔方就已经恢复原状,所以答案为 11。

输入数据 2

3
UR
FUL
LUF

输出数据 2

105
80
84

这组样例说明,不同面的旋转复合后可能产生较长的循环,并且改变操作顺序可能改变答案。

时间限制: C/C++C/C++ 不超过 1s1s;JavaJava 不超过 2s2s;PythonPython 不超过 3s3s。
内存限制: C/C++C/C++ 不超过 256MB256MB;JavaJava 不超过 384MB384MB;PythonPython 不超过 512MB512MB。