곱의 합 전개

수학자들은 프로그래머와 달리 하나의 소문자를 변수로 사용해 식을 씁니다. 덧셈은 더하기 기호 +로 나타내고, 곱셈은 변수나 부분식을 아무 기호 없이 나란히 붙여서 나타냅니다. 괄호로 묶은 덧셈이 아니라면, 곱셈이 덧셈보다 먼저 계산됩니다.

이 문제에서 식은 오직 변수, 덧셈, 곱셈, 괄호만으로 이루어집니다. 그 밖의 기호는 없습니다. 즉 공백, 나눗셈, 뺄셈, 숫자는 입력에도 출력에도 나타나지 않습니다. 예를 들어 다음은 모두 올바른 식입니다.

a+b+c
xyz
xyz+ab+cd
(a+b)(c+d)e

각 식에 대해 대수 법칙(분배 법칙)을 적용하여 괄호를 모두 없애고, 동치인 "곱의 합" 형태로 바꾸어야 합니다. 예를 들어 (a+b)(c+d)e 는 ace+ade+bce+bde 와 동치입니다.

같은 항끼리 합치지 않습니다. 출력에는 숫자가 없으므로 애초에 합칠 수도 없습니다. 즉 식을 완전히 전개했을 때 나오는 모든 항을 중복까지 포함하여 그대로 남깁니다. 답을 유일하게 만들기 위해, 각 항 안의 변수 순서와 항들의 순서는 아래 출력 형식에서 정한 표준 순서를 따릅니다.

첫 번째 줄에 식의 개수 $n$ 이 주어집니다. 이어지는 $n$ 개의 줄에는 위에서 설명한 올바른 식이 한 줄에 하나씩 주어집니다. 각 식의 길이는 $100$ 자를 넘지 않습니다.

총 $n$ 개의 줄을 출력합니다. 입력의 $i$ 번째 식을 완전히 전개한 "곱의 합"을 괄호 없이 $i$ 번째 줄에 출력하되, 답이 유일해지도록 아래 표준 형식을 지킵니다.

• 괄호가 남지 않을 때까지 분배 법칙을 적용하여 식을 여러 개의 항(변수들의 곱)의 합으로 전개합니다.
• 같은 항을 합치지 않습니다. 전개로 생긴 모든 항을 중복까지 포함하여 남깁니다.
• 각 항 안에서는 변수들을 알파벳 오름차순으로 나열합니다.
• 항들은 사전식(오름차순) 순서로 정렬하여 + 로 이어 붙입니다.

예를 들어 (a+b)(c+d)e 는 네 개의 항 ace, ade, bce, bde 로 전개되며, 각 항이 이미 알파벳 순이고 항들도 사전식 순서이므로 답은 ace+ade+bce+bde 입니다.