设 $f(s)$ 为字符串 $s$ 的哈希函数。若 $s = s_0s_1 \dots s_{n-1}$，则 $f(s) = \left( \sum_{i=0}^{n-1} w(s_i) \cdot \text{base}^i \right) \pmod r$。

Teacher Mai 想要找到两个不同的正则括号序列 $a$ 和 $b$，要求它们的长度 $l \le 10^4$ 且哈希值相同 ($f(a) = f(b)$)，其中 $w(\text{'('}) = p$，$w(\text{')'}) = q$。

我们按如下方式定义正则括号序列：空序列是正则序列。若 $S$ 是正则序列，则 $(S)$ 是正则序列。若 $A$ 和 $B$ 是正则序列，则 $AB$ 是正则序列。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。

存在多个测试用例。所有测试用例均为随机生成。对于每个测试用例，输入一行包含四个数字 $p, q, r, \text{base}$ ($1 \le p, q, r, \text{base} \le 10^{18}$)。

输出格式

对于每个测试用例，输出两个不同的正则括号序列 $a$ 和 $b$，要求它们的长度相同且不超过 $10^4$，并且哈希值相同 $f(a) = f(b)$。

样例

输入 1

1
4 7 37 10

输出 1

((()))
()()()