Woburn Challenge 2002

Problem 2: Intercepted Cowmmunication

Finally, the monkeys have made a breakthrough. During a routine trip to the
summit of the Enchanted Tree to gather sustenance (in the form of bananas) for
the Head-Monkey, a "Tiny" helper-monkey found a sheet of paper, left behind by
some cows, discussing their plan of attack against the monkeys. Now Tiny was a
clever little monkey and knew to deliver this information to the Head-Monkey
in order to receive a reward. Upon delivery, Tiny did receive his reward: An
assignment to code a neural net in 5 minutes flat, or risk having his fur
shaved off, in a frenzy of monkey excitement.

Anyways… It turns out that the note was written in some kind of code
that, appropriately enough, had to be decoded. The Head-Monkey summoned the
legendary Big-White Monkey, to help her with the decryption algorithm. They
used the classic decryption strategy of "Put yourself in the encoder's shoes".
Working with the knowledge that Bo Vine is a clever cow and a simple encryption
would be beneath him, they concluded that to decrypt the message, they have to
determine whether the parentheses are correctly nested. As an example, in the
sequence { a [ ] ( m, ) ] bb }, the parentheses are NOT properly
nested. Knowing this information, the Big-White Monkey can calculate the exact
day that the cows will attack, using algorithms known only to the MIT species.

Input

The first line of input contains a single integer, T
(1 ≤ T ≤ 50), indicating the number of test cases.
Each test case consists of a single line of text of at most 250 characters.
Note that the only legal parentheses are: (, ), [, ], {, }, <, >.

Output

A single word, TRUE or FALSE indicating whether parentheses are
properly nested or not.