魔方复原 Large

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

现在给出一个很长的由基本操作组合成的操作序列，你需要求出这个操作序列重复多少次之后魔方会第一次恢复到初始状态。

所谓恢复到初始状态是指当前每个方块的位置和初始每个方块的位置是相同的。

这个表示操作序列的字符串仅包含大写字母、、、、、，并且被表示为一个压缩后的形式。

假设用、、……这样的形式来表示一个被压缩了的字符串，那么任何一个其他的被压缩过的字符串都可以被表示为下列的某一种形式：

1、 可以是任何一个只由大写字母、、、、、组成的字符串；

2、 可以被表示为另一个字符串重复多次的形式。具体来说，可以被表示为“”这样的形式，用来表示被连续重复次；

3、 可以被表示成一些字符串首尾相连的形式。具体来说，可以被表示为“”这样的形式，表示、、……、这些字符串首尾相连；

4、一个空字符串(“”)也是一种合法的形式。

更为正规地，可以使用Backus-Naur From (BNF)来描述：

<compressed>::=“”|<letter>|<compressed><compressed>|<number>“(”<compressed>“)”

第一行是一个正整数，表示测试数据的组数，

对于每组测试数据，

输入只有一行，包含一个字符串，表示压缩后的操作序列，保证输入合法，且。

对于每组测试数据，

输出一行，包含一个整数，表示操作序列的重复次数，如果不能复原，输出。

1
D2(L3(UB))2(F)

12