공통 다항식

한 변수 $x$에 대한 다항식 중에서 모든 계수가 정수인 다항식을 정수 다항식이라고 한다.

두 정수 다항식 $A$, $B$에 대하여, 어떤 정수 다항식 $X$, $Y$가 존재하여 $A = C \cdot X$이고 $B = C \cdot Y$가 되는 정수 다항식 $C$를 $A$와 $B$의 공약수라고 부른다.

두 다항식의 최대공약수는 이러한 공약수 중에서 차수가 가장 큰 것을 뜻한다. 상수배를 무시하면 최대공약수는 유일하게 정해진다. 즉 $C$와 $D$가 모두 $A$, $B$의 최대공약수이면, $p \cdot C = q \cdot D$를 만족하는 음이 아닌 정수 $p$, $q$가 존재한다.

두 정수 다항식 $A$, $B$가 주어질 때 이들의 최대공약수를 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스는 두 줄로 이루어지며, 각 줄에 다항식이 하나씩 주어진다. 다항식은 다음 규칙에 따라 표기된다.

1. 기본항은 변수 x, 상수(숫자 0~9), 또는 괄호로 감싼 식이다. 예: x, 99, (x+1)
2. 인수는 기본항 뒤에 ^와 지수(숫자)를 붙여 나타낸다. 예: 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 \times 9$가 아니라 $99$이다.

입력으로 주어진 다항식을 모두 전개했을 때, 각 계수는 $100$ 이하이고 $x$의 차수는 $10$ 이하이다. ^ 뒤에 오는 지수는 항상 음이 아닌 정수이다. 올바르게 계산했을 때 32비트 정수로 계산할 수 있는 데이터만 주어진다(오버플로가 없다).

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

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

$c_i$는 양의 정수, $p_i$는 음이 아닌 정수이며 $p_0 > p_1 > \dots > p_n$을 만족한다. 계수들의 최대공약수 $\gcd(c_0, \dots, c_n)$은 $1$이다. 각 항 사이의 ±는 그 항 계수의 부호에 따라 + 또는 -가 되고, 첫 항 $c_0 x^{p_0}$ 앞에는 부호를 붙이지 않는다.

또한 다음 규칙을 지켜야 한다.

1. $c_i$가 $1$이고 $p_i$가 $0$이 아니면 $c_i$를 생략한다.
2. $x^0$은 생략한다.
3. $x^1$은 x로 쓴다.