题目描述
Fran didn’t pay attention in school during chemistry class and now he needs your help in doing his homework. His homework consists of n chemical equations for which he needs to check if they are balanced. A chemical equation is a way of representing chemical reactions using symbols and formulas. In a chemical reaction, some set of initial molecules react to produce a new set of molecules.
A chemical equation has a left side and a right side. The left side contains chemical formulas of the initial molecules, while the right side contains chemical formulas of the product molecules. The left and the right sides of the equation are separated by an arrow (characters ->). Different molecules appearing on the left or the right side are separated by a +.
Molecules are substances made from atoms, tiny particles which are denoted with capital letters of the Latin alphabet (for the purposes of this task). The formula of a molecule is written by listing the labels of all the different atoms which make up the molecule. If a molecule has multiple instances of some atom, then the number of occurrences of this atom is written after the atom in the formula. For example, AC4B is a formula for a molecule which has one atom A, 4 atoms C and one atom B. If on one side of the equation a molecule appears more than once, then this number of occurrences is written as a coefficient in front of the formula. For example, 3AC4B denotes 3 molecules of AC4B, for a total of 3 atoms A, 12 atoms C and 3 atoms B.
A chemical equation is said to be balanced if the right side and the left side contain an equal number of atoms of each kind. Your task is to determine whether or not each of the n chemical equations is balanced. The test cases will be such that all the numbers appearing in the reactions (the numbers of atoms in molecules and the numbers of molecules in the ractions) will have only a single digit (and they will be larger than 1).
输入
The first line contains a positive integer n (1 ≤ n ≤ 10), the number of chemical equations. Each of the next n lines contains a sequence of characters representing a chemical equation. Each equation consists of at most 1000 characters. The equations will not necessarily be balanced, but they will be correctly written as described in the statement.
输出
For each of the n equations print DA if it is balanced, and NE if it is not, in separate lines.
【样例输入1】
3
A+B->AB
AB+CD->AC+DB
AB+B->AB
【样例输入2】
2
2AB+A->3AB
2AB+2AC+2BC->4ABC
【样例输入3】
4
2H2O+2CO2->2H2CO3
H2SO4->H2O4
NH3+H2SO4->NH4SO4
CH4+2O2->CO2+2H2O
【样例输出1】
DA
DA
NE
【样例输出2】
NE
DA
【样例输出3】
DA
NE
NE
DA
提示
Clarification of the third example:
First equation: both sides have 4 atoms H, 2 atoms C and 6 atoms O so the answer is DA.
Second equation: the left side has a single S atom, but the right side has none so the answer is NE.
Third equation: the left side has 5 atoms H, but the right side has 4 so the answer is NE.
Forth equation: both sides have 4 atoms H, one atom C and 4 atoms O so the answer is DA.