괄호 최소화

사칙연산 기호와 괄호, 그리고 빈칸을 나타내는 x로만 이루어진 산술식 템플릿 $w$가 있다. 예를 들어 (x*x)/(x+x)는 올바른 템플릿이다.

템플릿의 대입이란 빈칸마다 실수를 하나씩 넣어 식의 값이 정의되도록 만드는 것이다. 위 템플릿의 빈칸에 왼쪽부터 1, 2, 3, 4를 넣으면 식의 값은 $(1 \times 2)/(3+4) = 2/7$이다. 1, 2, 3, -3을 넣으면 분모가 0이 되어 값이 정의되지 않으므로 이것은 대입이 아니다.

두 템플릿 $w$와 $w'$가 다음 세 조건을 모두 만족하면 두 템플릿은 동치이다.

• 두 템플릿의 대입 집합이 같다.
• 모든 대입에서 두 식의 값이 같다.
• 한 템플릿에서 괄호 몇 개를 지워 다른 템플릿을 얻을 수 있다.

(x*x)/(x+x)와 x*x/(x+x)는 동치이다. 반면 (x*x)/(x+x)와 x*x/x+x는 1, 2, 3, 4를 대입한 값이 각각 $2/7$과 $14/3$이므로 동치가 아니다. x-(x-x)와 x-x+x도 동치가 아니다. 괄호만 지워서는 한쪽에서 다른 쪽을 얻을 수 없기 때문이다.

주어진 템플릿과 동치인 템플릿 가운데 괄호가 가장 적은 것을 구하여라.

곱셈과 나눗셈의 우선순위는 서로 같고, 덧셈과 뺄셈보다 높다. 따라서 곱셈과 나눗셈을 덧셈과 뺄셈보다 먼저 계산한다. 덧셈과 뺄셈의 우선순위도 서로 같다. 우선순위가 같은 연산은 왼쪽부터 차례로 계산한다.

첫째 줄에 템플릿의 개수 $n$이 주어진다. 다음 $n$개 줄에 템플릿이 한 줄에 하나씩 주어진다. 각 템플릿은 비어 있지 않고 문법에 맞으며, +, -, *, /, (, ), x 문자로만 이루어진다. 여기서 x는 빈칸이다. 모든 템플릿의 길이의 합은 $10^6$ 이하이다.

$n$개의 줄을 출력한다. $i$번째 줄에는 입력의 $i$번째 템플릿과 동치인 템플릿 가운데 괄호가 가장 적은 것을 출력한다. 이 템플릿은 유일하다.