Merge Overlapping Intervals

You are given several test cases. In each test case, you are provided with a list of intervals. Each interval is represented by two integers indicating the start and end points. Your task is to merge all overlapping intervals and then output the merged intervals in a specific format.

An interval [a, b] and [c, d] are considered overlapping if \( b \ge c \). After merging, the resulting interval will be \( [\min(a,c), \max(b,d)] \).

Note: If there are no intervals in a test case, output an empty line.

inputFormat

The input is read from standard input (stdin) with the following format:

T
N1
s11 e11
s12 e12
... 
N2
s21 e21
s22 e22
...
...

Here:

• T is the number of test cases.
• For each test case, the first line contains an integer N, the number of intervals.
• Then N lines follow, each containing two integers representing the start and end of an interval.

outputFormat

For each test case, output a single line to standard output (stdout) containing the merged intervals. Each merged interval should be printed in the format (a b) (with a single space between the numbers) and intervals should be separated by a single space. If there are no intervals in a test case, output an empty line.

## sample

4
4
1 3
2 4
5 7
6 8
2
1 4
4 5
3
1 4
2 3
7 9
0

(1 4) (5 8)
(1 5)
(1 4) (7 9)

</p>