디지털 어니언

디지털 어니언(Digital Onion, 줄여서 DO)은 괄호로만 이루어진 문자열이다. 다음과 같이 재귀적으로 정의한다.

1. 빈 문자열(괄호가 하나도 없는 경우)은 DO이며, 이를 널 DO라고 한다.
2. ()는 DO이며, 이를 기본 DO라고 한다.
3. A와 B가 모두 DO이면 (A)B도 DO이다. 이때 A를 그 DO의 안쪽, B를 바깥쪽이라고 한다.

예를 들어 (())()와 ((()))(()()())는 DO이지만, ()())((와 ((())는 DO가 아니다.

DO의 무게는 그 안에 들어 있는 (의 개수(즉 )의 개수)로 정의한다. 널 DO의 무게는 0, 기본 DO ()의 무게는 1이며, ((()))(()()())의 무게는 7이다.

X = ((()))(()()())이면 X의 안쪽은 (()), 바깥쪽은 (()()())이다. X = (()(()))이면 안쪽은 ()(())이고 바깥쪽은 널 DO이다.

이제 모든 DO에 가격 순서를 다음 세 규칙으로 정한다.

• 규칙 1. 무게가 클수록 더 비싸다.
• 규칙 2. 무게가 같으면 안쪽 DO가 더 비싼 쪽이 더 비싸다.
• 규칙 3. 무게가 같고 안쪽 DO의 가격도 같으면 바깥쪽 DO가 더 비싼 쪽이 더 비싸다.

B가 A보다 비쌀 때 A < B로 쓴다. 예를 들어 규칙 1에 의해 () < (()), (())() < ((()))()이고, 규칙 2에 의해 (())(()) < ((()))()이며, 규칙 3에 의해 (())()() < (())(())이다.

DO X가 주어지면, X보다 비싸면서 그 둘 사이의 가격을 가지는 DO가 존재하지 않는 DO, 즉 다음으로 비싼 DO(NMED, Next More Expensive DO)를 출력하라. 다시 말해 모든 DO를 가격순으로 정렬했을 때 X 바로 다음에 오는 DO이다.

첫째 줄에 테스트 케이스의 수 T가 주어진다. 이어지는 T개의 줄에 각각 하나의 DO가 주어진다. 각 줄의 끝은 $로 표시하며, 모든 (, ), 그리고 마지막 $ 사이에는 적어도 하나의 공백이 있다. 입력으로 주어지는 각 DO의 무게는 1 이상 30 이하이다.

각 테스트 케이스마다 한 줄에 다음으로 비싼 DO를 출력하고 그 뒤에 끝 표시 $를 붙인다. 입력과 마찬가지로 모든 (, ), 그리고 $는 하나의 공백으로 구분한다.