Balanced Chemical Equations

You are given n chemical equations. Each chemical equation is represented as a string in the following format:

The equation is divided into two parts separated by an equals sign (=). In each part, one or more molecules appear, and multiple molecules are concatenated using a plus sign (+).

Each molecule may have an optional leading coefficient which indicates the number of that molecule participating in the reaction. The molecule itself is a concatenation of atoms. Each atom is represented by an uppercase letter immediately followed by a digit indicating the count of that atom (if the digit is missing, its count is assumed to be 1). For example, the molecule 3AC4B should be interpreted as having a coefficient of 3 multiplying the molecule AC4B. In the molecule AC4B, the atom A appears once, C appears 4 times, and B appears once. Thus, overall there are 3 of A, 12 of C, and 3 of B participating in the reaction.

Your task is to check whether the chemical equation is balanced i.e. whether for each type of atom the total count on the left-hand side equals the total count on the right-hand side.

Note: You only need to check the balance of atom counts; you do not need to worry about the chemical validity of the equation.

inputFormat

The first line contains an integer n (1 ≤ n ≤ 100) — the number of chemical equations.

Then follow n lines, each containing a chemical equation in the format described above.

Each equation consists of a left-hand side and a right-hand side separated by an equals sign (=). Within each side, molecules are separated by plus signs (+).

outputFormat

For each equation, output a single line. Print balanced if the equation is balanced, otherwise print not balanced.

sample

4
3AC4B=AC4B+AC4B+AC4B
A2B+3C=2A+B+3C
2A+3B=2B+3A
AC+B2=AC+B2

balanced
balanced
not balanced
balanced