공통 다항식

김동규 수학 선생님은 매주 토요일마다 학생들에게 수학을 가르쳐준다. 2주 전에는 1변수 다항식(변수가 x 하나)을 설명했고, 지난주에는 다항식의 최대공약수를 구하는 법을 설명하고 두 다항식의 최대공약수를 구하는 숙제를 내주었다.

동규는 FM2013을 하느라 숙제를 채점할 시간이 없었으므로, 자동으로 채점을 해주는 프로그램을 만들려고 한다.

동규가 숙제로 내준 다항식의 계수는 모두 정수이고, 이를 정수 다항식이라고 부른다.

두 정수 다항식 A와 B가 있을 때, 임의의 정수 다항식 X, Y에 대해서, A=CX, B=CY를 만족하는 정수 다항식 C를 A와 B의 공약수라고 부른다.

두 다항식의 최대공약수는 공약수중 다항식의 차수가 가장 큰 것을 말한다. 또, 상수항을 무시하다면, 두 다항식의 최대공약수는 유일하다. 즉, C와 D가 다항식 A와 B의 최대공약수일 때, p×C = q×D를 만족하는 음이아닌 정수 p와 q가 있다는 뜻이다.

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 두 줄로 이루어져 있고, 다음과 같은 다항식이 입력으로 주어진다.

1. 다항식의 기본항은 변수 x, 상수(0-9), 또는 괄호로 감싸진 식이다. 예)x, 99, (x+1)
2. 다항식의 인수는 기본항 뒤에 ^를 붙이고 숫자(0-9)로 나타낸다. 예) x^05, 1^15, (x+1)^3
3. 다항식의 항은 여러 인수의 곱으로 나타낸다. 예) 4x, (x+1)(x-2), 3(x+1)^2
4. 다항식은 하나 또는 그 이상의 항을 + 또는 -로 연결한다. 첫 항은 -로 시작할 수 있다. 예) -x+1, 3(x+1)^2-x(x-1)^2

상수 여러개가 붙여져서 주어지는 경우, 이를 그대로 상수로 이용하면 된다. 즉, 99는 9*9가 아니고 99이다.

입력으로 받은 다항식을 모두 펼쳤을 때, 다항식의 계수는 100보다 작거나 같고, x의 차수는 10보다 작거나 같다. 제곱에 나타나는 상수는 항상 음이 아닌 값이다.

올바르게 계산했을 때, 32비트 정수로 계산할 수 있는 데이터만 주어진다. (overflow가 없음)

각각의 테스트 케이스에 대해서 입력으로 주어진 두 다항식의 최대공약수를 다음과 같은 형식으로 출력한다.

c0x^p0±c1x^p1...±cnx^pn

ci와 pi(i=0,...,n)는 양의 정수이고, p0>p1>...>pn을 만족한다. {ci|i=0,...n}의 최대공약수는 1이다.

또한 다음과 같은 규칙을 지켜야 한다.

1. ci가 1일 때, pi가 0이 아니면 생략해야 한다.
2. x^0은 생략해야 한다.
3. x^1은 x로 출력해야 한다.