Balanced Parentheses Checker

In this problem, you are given a string consisting solely of the characters '(' and ')'. Your task is to determine whether the sequence of parentheses is balanced. A sequence is considered balanced if every opening parenthesis '(' is eventually closed by a corresponding closing parenthesis ')' and the order of the parentheses is correct. Formally, if we scan the string from left to right, the count of closing parentheses should never exceed the count of opening ones, and the total counts must be equal by the end. An empty string is considered balanced.

The solution must read the input from standard input (stdin) and write the result to standard output (stdout). For each test case, output "BALANCED" if the string is balanced, and "NOT BALANCED" otherwise.

The balance condition can be expressed as: (\forall s, \quad\text{if }balance(s)=0 \text{ and } balance \ge 0 \text{ during scanning, then s is balanced.})

inputFormat

The first line contains an integer (T) representing the number of test cases. Each of the following (T) lines contains a string composed only of '(' and ')'.

outputFormat

For each test case, output a single line with either "BALANCED" or "NOT BALANCED" depending on whether the input string is balanced.## sample

3
(())
(()
()()()

BALANCED
NOT BALANCED
BALANCED