Common Polynomial

Time limit1sMemory limit128 MB

Summary

Parse two polynomial expressions with parentheses and exponents, expand them, then compute and print the normalized greatest common divisor polynomial.

Level: Medium7 of 10
Topics: Math, Recursion, Implementation
Solved: No attempts yet

Problem

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.

Input

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.

A primary term is the variable x, a constant (digits 0~9), or an expression enclosed in parentheses. Examples: x, 99, (x+1)
A factor is a primary term followed by ^ and an exponent (digits). Examples: x^05, 1^15, (x+1)^3
A term is a product of one or more factors. Examples: 4x, (x+1)(x-2), 3(x+1)^2
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.

Output

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.

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

Examples7

Example 1

Input

3
-(x^3-3x^2+3x-1)
(x-1)^2
x^2+10x+25
x^2+6x+5
x^3+1
x-1

Expected output

x^2-2x+1
x+5
1

Example 2
Input
```
1
x^2-1
x-1
```
Expected output
```
x-1
```
Example 3
Input
```
1
x
x+1
```
Expected output
```
1
```
Example 4
Input
```
1
2x+2
4x+4
```
Expected output
```
x+1
```
Example 5
Input
```
1
-x^2+1
x-1
```
Expected output
```
x-1
```
Example 6
Input
```
1
(x-1)^2(x+2)
(x-1)(x+2)^2
```
Expected output
```
x^2+x-2
```
Example 7
Input
```
1
x^05
x^02
```
Expected output
```
x^2
```