Cow Cotillion

The cow cotillion is a fancy spring dance in which the cows (written as >) and the bulls (written as <) bow to each other. A single, properly bowing pair is written ><.

Sometimes another pair sashays between a bowing pair, giving > >< < (that is, >><<). Larger groups can mix on the dance floor, such as > >< < ><, which adds a second bowing pair on the right.

Even complex arrangements can be perfectly legal formations:

> > > >< < >< < >< >< >< <

| | | -- | -- | -- -- -- |
| | ------    |          |
| -------------          |
--------------------------

Sometimes a stray heifer sneaks into a group and unbalances it, for example > >< < <><. This is strictly forbidden.

Farmer John records dance lines of up to 500 cattle and wonders whether each line is properly balanced — that is, whether every animal can be paired off, in at least one way, as a properly bowing >< pair. He writes down only the direction each animal bows, with no spaces; for instance, the illegal line above becomes >><<<><.

Equivalently, treat > as an opening bracket and < as a closing bracket: a line is legal exactly when the brackets are balanced (scanning left to right, every < matches an earlier still-unmatched >, and no animal is left unmatched).

You are given $N$ recordings. Each recording is a string $P$ made up only of the characters > and <. For each recording, print legal if all the cattle can be paired into proper bowing pairs, and illegal otherwise.

Constraints

• $1 \le N \le 1000$
• Each pattern has length $K$ with $1 \le K \le 200$.

• Line 1: a single integer $N$.
• Lines $2 \ldots N+1$: line $i$ contains an integer $K_i$, a space, and a string of $K_i$ characters (each > or <) — the length $K_i$ and the pattern $P_i$.

• Lines $1 \ldots N$: line $i$ contains legal if pattern $P_i$ forms a valid bowing configuration, or illegal otherwise.