시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 1024 MB267522413.793%

문제

괄호 문자열은 다음과 같은 3개의 조건만으로 만들 수 있는 문자열을 말한다.

  • 빈 문자열은 괄호 문자열이다.
  • 괄호 문자열 a에 대해 (a)는 괄호 문자열이다.
  • 두 괄호 문자열 a, b에 대해 ab는 괄호 문자열이다.

괄호 문자열의 예시로는 (())(), (((()())())()), ((()())()()())(()) 등이 있다.

다음과 같은 방법으로 괄호 문자열이 나타내는 값을 정한다.

  • 빈 문자열이 나타내는 값은 1이다.
  • 괄호 문자열 a가 나타내는 값이 x라 할 때, (a)가 나타내는 값은 x + 1이다.
  • 두 괄호 문자열 a, b가 나타내는 값이 각각 x, y라 할 때, ab가 나타내는 값은 x × y이다.

예를 들어 (())()는 6을 나타낸다.

  • ()는 1 + 1 = 2를 나타낸다.
  • (())는 2 + 1 = 3을 나타낸다.
  • (())()는 3 × 2 = 6을 나타낸다.

자연수 N이 주어지면 N을 나타내는 가장 짧은 괄호 문자열을 구해보자. 단, 그러한 문자열이 여러 개 있으면 사전 순으로 가장 앞서는 것을 구한다.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. (1 ≤ T ≤ 20)

둘째 줄부터 각 테스트 케이스 별로 한 줄에 하나씩 자연수 N이 주어진다. (2 ≤ N ≤ 1,000,000 = 106)

출력

첫째 줄부터 각 테스트 케이스 별로 한 줄에 하나씩 N을 나타내는 가장 짧은 괄호 문자열을 출력한다. 단, 그러한 문자열이 여러 개 있으면 사전 순으로 가장 앞서는 것을 출력한다.

예제 입력 1

3
6
23
123

예제 출력 1

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

예제 입력 2

6
987997
9879
98799
98
987
9

예제 출력 2

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

출처