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⩽t⩽5.
1⩽x⩽1,000,000.
For the first testcase, the bracket sequences "(())", "()()" are the only bracket sequences of length 4 (which is minimal) with exactly 4 repeated subsequences.
For "(())", there are 4 subsequences that form "()".
For "()()", there are 3 subsequences that form "()" and 1 subsequence that form "()()".
For the second testcase, the bracket sequences "((()", "()))" are the only bracket sequences of length 4 (which is minimal) with exactly 3 repeated subsequences.
For both of them, there are exactly 3 subsequences that form "()".
