设集合 $\Sigma$ 由所有长度为 1 到 4 的小写字母组成的单词构成，例如单词 "a"、"b"、"f"、"aa"、"fun" 和 "kvqf"。考虑符合以下两条规则的文法所生成的表达式：

$$E \to f$$ $$E \to f(E,E)$$

其中 $f \in \Sigma$。任何表达式都可以根据其语法轻松地表示为一棵树。

例如，表达式 a(b(f(a,a),b(f(a,a),f)),f(b(f(a,a),b(f(a,a),f)),f)) 由下图左侧的树表示：

昨晚你梦见了一个伟大的发明，它可以大大减小表示的规模：使用图而不是树，来共享公共子表达式。例如，上述表达式可以用图右侧的图来表示。虽然树包含 21 个节点，但该图仅包含 7 个节点。

由于左侧的树本身也是一个图，因此使用图的表示方法并不唯一。给定一个表达式，请找到一个节点数尽可能少的图来表示该表达式！

输入格式

输入的第一行包含一个整数 $c$ ($1 \le c \le 200$)，表示表达式的数量。

接下来的 $c$ 行，每行包含一个符合上述文法的表达式，不包含任何空格。其对应的树表示最多包含 $50\,000$ 个节点。

输出格式

对于每个表达式，输出单行，包含一个节点数尽可能少的图表示。

图表示以字符串形式写出，方法是将相应的子表达式替换为数字。每个数字指向应插入该位置的子表达式的根节点。节点按在字符串中出现的顺序从 1 开始依次编号；此编号仅包括图中的节点（不包括已被数字替换的节点）。数字必须指向之前已经写出的节点（不允许前向引用）。对于我们的示例，我们得到 a(b(f(a,4),b(3,f)),f(2,6))。

样例

输入样例 1

3
this(is(a,tiny),tree)
a(b(f(a,a),b(f(a,a),f)),f(b(f(a,a),b(f(a,a),f)),f))
z(zz(zzzz(zz,z),zzzz(zz,z)),zzzz(zz(zzzz(zz,z),zzzz(zz,z)),z))

输出样例 1

this(is(a,tiny),tree)
a(b(f(a,4),b(3,f)),f(2,6))
z(zz(zzzz(zz,z),3),zzzz(2,5))