Common Polynomial

Among polynomials in a single variable $x$, one whose coefficients are all integers is called an integer polynomial.

Given two integer polynomials $A$ and $B$, an integer polynomial $C$ is called a common divisor of $A$ and $B$ if there exist integer polynomials $X$ and $Y$ such that $A = C \cdot X$ and $B = C \cdot Y$.

The greatest common divisor of the two polynomials is the common divisor of the highest degree. Ignoring a constant multiple, the greatest common divisor is unique: if both $C$ and $D$ are greatest common divisors of $A$ and $B$, then there exist non-negative integers $p$ and $q$ with $p \cdot C = q \cdot D$.

Given two integer polynomials $A$ and $B$, write a program that computes their greatest common divisor.

The first line contains the number of test cases $T$. Each test case consists of two lines, each containing one polynomial. A polynomial is written according to the following rules.

1. A primary term is the variable x, a constant (digits 0~9), or an expression enclosed in parentheses. Examples: x, 99, (x+1)
2. A factor is a primary term followed by ^ and an exponent (digits). Examples: x^05, 1^15, (x+1)^3
3. A term is a product of one or more factors. Examples: 4x, (x+1)(x-2), 3(x+1)^2
4. A polynomial is one or more terms joined by + or -. The first term may begin with -. Examples: -x+1, 3(x+1)^2-x(x-1)^2

When several digits are written together, they form a single constant. That is, 99 means $99$, not $9 \times 9$.

When every input polynomial is fully expanded, each coefficient is at most $100$ and the degree of $x$ is at most $10$. Every exponent written after ^ is a non-negative integer. Only data that can be computed with 32-bit integers is given, so a correct computation does not overflow.

For each test case, print the greatest common divisor of the two polynomials in the following format.

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

Each $c_i$ is a positive integer, each $p_i$ is a non-negative integer, and $p_0 > p_1 > \dots > p_n$. The greatest common divisor of the coefficients, $\gcd(c_0, \dots, c_n)$, is $1$. Each ± between terms is + or - according to the sign of that term's coefficient, and the first term $c_0 x^{p_0}$ is written without a leading sign.

In addition, follow these rules.

1. If $c_i$ is $1$ and $p_i$ is not $0$, omit $c_i$.
2. Omit $x^0$.
3. Write $x^1$ as x.