Equality Test

Numeric Regular Expression (NRE) is a simple version of regular expression. It is a useful tool for numeric string matching.

If S is an NRE, we often use function L(S) to represent the set of numeric strings matched by S. Note that L(S) maybe infinite.

NRE and function L can be recursively defined by the following rules:

1. Atom: A single digit (0,1,2,...,9) is an NRE, and L(d)={d}, where d=0,1,2,...9.

2. Nestification: If x is an NRE, then (x) is an NRE, and L((x))=L(x).

3. Concatenation: If x and y are NREs, then xy is an NRE, and L(xy)={ab | a∈x and b∈y}.

4. Option: If x and y are NREs, then x|y is an NRE, and L(x|y)= L(x)∪L(y).

5. Closure: If x is an NRE, then x* is an NRE, and L(x*)={ε, L(x),L(xx),L(xxx),...}, hereε means “empty string”. In other word, x* matches x zero or more times.

To avoid confusion, the order of operations (from high to low) is: nestification, closure, concatenation and option. Operations with higher order will be applied first, and same operations will be applied from left to right. For example,01* is equal to 0(1*), not (01)*; 00|1 is equal to (00)|1, not 0(0|1).

Now give you two NERs r1 and r2, can you tell us whether L(r1)=L(r2) or not?

There are several test cases in the input.

The first line contains an integer T (1 <= T <= 50) -- the number of test cases.

Each test case contains two lines, the first line is r1 and the second line is r2 (1 <= |r1|,|r2| <= 10). It is guaranteed that both r1 and r2 are correct NREs without any useless character.

For each test case, output the answer “YES” or “NO” in a single line.

2
(1|2)*
(2|1)*
34|2
32|4

YES
NO

2014 ACM/ICPC Asia Regional Guangzhou Online