描述

字符串的**循环旋转集合**是将字符串顺时针嵌入环中得到的字符串集合：将字符串首尾相连形成环，从任意字符位置开始顺时针遍历，直到回到起始位置的前一个字符为止。若一个字符串是其所有循环旋转中字典序最小的，则称其为**项链**。例如，字符串$01011$的循环旋转为$(10110, 01101, 11010, 10101, 01011)$，其中$01011$是最小字符串，因此是一个项链。

任意字符串$S$均可唯一表示为项链$T_1T_2\ldots T_k$的连接，满足：

• 对所有$i=1,\ldots,k-1$，有$T_{i+1} < T_i$；
• 对所有$i=1,\ldots,k-1$，$T_iT_{i+1}$不是项链。
  这种表示称为字符串$S$的项链分解，你的任务是找到该分解。

字符串上的关系$<$是字典序，定义为：若$A$是$B$的真前缀，或$A$与$B$的前$j-1$位相同但第$j$位更小，则$A < B$。例如，$001 < 0010$，$1101011 < 1101100$。

输入

输入第一行是一个正整数$n$，表示测试用例的数量。每个用例包含一行非空的01字符串，长度不超过$100$。

输出

对每个用例，输出一行字符串的项链分解，每个项链用括号包裹，格式为(项链)。

输入数据1

5  
0  
0101  
0001  
0010  
11101111011  

输出数据1

(0)  
(0101)  
(0001)  
(001)(0)  
(111)(01111)(011)  

来源

2005年北欧竞赛