Lazy Math Instructor

Time limit1sMemory limit128 MB

Summary

Decide whether two arithmetic expressions with left-to-right equal-precedence operators are identical as polynomials over single-letter variables.

Level: Medium7 of 10
Topics: Hash map, String, Math, Implementation
Solved: No attempts yet

Problem

A math instructor is too lazy to grade exam questions that ask students to derive a complicated formula. Students write correct answers in many different forms, which makes grading very hard, so the instructor needs help from programmers.

Write a program that reads two formulas and determines whether they are arithmetically equivalent, that is, whether they always evaluate to the same value.

Input

The first line contains an integer $N$ ( $1 \le N \le 20$ ), the number of test cases. Each test case is then given on two lines, and each line holds one arithmetic expression of at most 80 characters. The input contains no blank lines.

Each expression consists of one or more of the following:

Single-letter variables (case insensitive, so A and a denote the same variable).
Single-digit numbers.
Matched left and right parentheses.
The binary operators +, -, and * for addition, subtraction, and multiplication.
Any number of blank or tab characters between tokens.

Every expression is syntactically correct. All operators have equal precedence and are evaluated from left to right; for example, a+b*c is the same as (a+b)*c. The coefficients and exponents of the variables that appear during evaluation are guaranteed to fit in 16-bit integers.

Output

Print one line for each test case: YES if the two expressions are arithmetically equivalent, and NO otherwise. The output must be entirely in upper-case.

Examples1

Example 1

Input

3
(a+b-c)*2
(a+a)+(b*2)-(3*c)+c
a*2-(a+c)+((a+c+e)*2)
3*a+c+(2*e)
(a-b)*(a-b)
(a*a)-(2*a*b)-(b*b)

Expected output

YES
YES
NO