One day, ZS the Coder asked Navi an interesting question :

"A bracket sequence is a string which only consists of the brackets '(' and ')'. A bracket sequence is called repeated if it is of the form "()()...()" (where "()" appears \(n > 0\) times), i.e. the string "()" concatenated n times. Given a string s, find the number of subsequences of s which are repeated."

Navi, being the top student in class, managed to solve this problem instantly. Now, he challenges ZS the Coder to solve the inverse of this problem :

"Given a positive integer x, find a bracket sequence of minimal length that has exactly x repeated bracket subsequences."

ZS the Coder is stumped by this problem. Can you help him solve it?

Input Format:
The input consists of t testcases. The first line contains a single integer t, denoting the number of testcases.

The next t lines of input contains a single integer each, denoting the value of x for each testcase.

Output Format:
For each testcase, output a bracket sequence of minimal length with exactly x repeated bracket subsequences. If there are multiple answers, any of them will be accepted.

Constraints:
\(1 \leqslant t \leqslant 5\).
\(1 \leqslant x \leqslant 1,000,000\).