405964: GYM102192 D Parentheses Matrix

A parentheses matrix is a matrix where every element is either '(' or ')'. We define the goodness of a parentheses matrix as the number of balanced rows (from left to right) and columns (from up to down). Note that:

• an empty sequence is balanced;
• if A is balanced, then (A) is also balanced;
• if A and B are balanced, then AB is also balanced.

For example, the following parentheses matrix is a 2 × 4 matrix with goodness 3, because the second row, the second column and the fourth column are balanced:

    )()(
    ()()

Now, give you the width and the height of the matrix, please construct a parentheses matrix with maximum goodness.

The first line of input is a single integer T (1 ≤ T ≤ 50), the number of test cases.

Each test case is a single line of two integers h, w (1 ≤ h, w ≤ 200), the height and the width of the matrix, respectively.

For each test case, display h lines, denoting the parentheses matrix you construct. Each line should contain exactly w characters, and each character should be either '(' or ')'. If multiple solutions exist, you may print any of them.

3
1 1
2 2
2 3

(
()
)(
(((
)))