Comparing Parenthesis Values

Time limit4sMemory limit1024 MB

Summary

Given two valid parenthesis strings, compare the values defined by f(()) = 1, f((X)) = 2 f(X), and f(XY) = f(X) + f(Y).

Level: Medium6 of 10
Topics: String, Stack, Implementation, Math
Solved: No attempts yet

Problem

Among strings made of opening parenthesis ( and closing parenthesis ), a valid parenthesis string is defined as follows.

The string (), consisting of a single pair of parentheses, is a valid parenthesis string.
If X is a valid parenthesis string, then (X), which wraps X in parentheses, is also a valid parenthesis string.
If X and Y are valid parenthesis strings, then XY, the concatenation of X and Y, is also a valid parenthesis string.
Every valid parenthesis string is built only through the three rules above.

For example, (()(())) and (())()() are valid parenthesis strings, but (() and )((()() are not. For a valid parenthesis string X, the value of the string (parenthesis value) is defined below and written as f[X].

f[()] = 1
If X is a valid parenthesis string, f[(X)] = 2 × f[X]
If X and Y are valid parenthesis strings, f[XY] = f[X] + f[Y]

For example, let us compute the parenthesis values of several valid parenthesis strings.

f[()] = 1
f[(())] = 2 × f[()] = 2 × 1 = 2
f[()()] = f[()] + f[()] = 1 + 1 = 2
f[()()()] = f[()] + f[()()] = 1 + 2 = 3
f[(()())] = 2 × f[()()] = 2 × 2 = 4
f[((()))] = 2 × f[(())] = 2 × 2 = 4
f[()(())] = f[()] + f[(())] = 1 + 2 = 3
f[(()())()(())] = f[(()())] + f[()(())] = 4 + 3 = 7

Write a program that reads two valid parenthesis strings A and B and compares the parenthesis values f[A] and f[B] of the two strings. In other words, write a program that determines whether f[A] = f[B], f[A] < f[B], or f[A] > f[B].

A single input must solve T test cases.

Input

The first line gives the number of test cases T.

Then T test cases follow in order. The format of each test case is as follows.

The first line gives A.
The second line gives B.

Output

For each test case, on one line, print

= if f[A] = f[B],
< if f[A] < f[B],
> if f[A] > f[B].

Constraints

1 ≤ T ≤ 10
A and B are valid parenthesis strings.
In a single input, the sum of the lengths of A over all test cases is at most 3 000 000.
In a single input, the sum of the lengths of B over all test cases is at most 3 000 000.

Examples3

Example 1
Input
```
1
(())
()()
```
Expected output
```
=
```
Example 2
Input
```
1
()()()
(()())
```
Expected output
```
<
```

Example 3

Input

2
((()))
()(())
(((())))
()()()()()

Expected output

>
>