Putata 正在使用他最喜欢的 IDE 编程。这个 IDE 最棒的部分是括号补全功能。 该功能的工作方式如下：假设屏幕上当前显示的是 $S|T$，其中 $|$ 是光标的当前位置，$S$ 和 $T$ 是两个（可能为空的）字符串。

• Putata 输入左括号 ‘(’，屏幕上将显示 $S(|)T$，其中 $|$ 是光标的新位置。
• Putata 输入右括号 ‘)’。如果 $T = )T'$，这意味着 $T$ 以右括号开头，那么字符串将不会改变，光标会移动到下一个字符的右侧，屏幕上将显示 $S)|T'$；否则，屏幕上将显示 $S)|T$。

Putata 昨晚工作得很辛苦，早上醒来时，他只记得电脑上保存的代码，以及他只输入了若干个括号。请帮他找出他输入的括号序列，或者告诉他仅通过输入括号是不可能打出这个字符串的。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^6$)，表示测试用例的数量。 对于每个测试用例，唯一的一行包含一个字符串 $S$ ($1 \le |S| \le 10^6$)。保证 $S$ 仅由括号 ‘(’ 和 ‘)’ 组成。 保证所有测试用例的 $|S|$ 之和不超过 $10^6$。

输出格式

对于每个测试用例，如果可以通过输入括号打出该字符串，则输出一行字符串，表示答案。否则，输出一行 “impossible”。如果存在多个答案，你可以输出其中任意一个。

请注意，你不需要最小化答案的长度。你的答案应仅包含括号，且如果答案存在，其长度不应超过对应测试用例的输入字符串长度。

样例

输入 1

3
((()))
(
)))()

输出 1

(((
impossible
)))(