Kemija

Time limit1sMemory limit512 MB

Summary

Given chemical equations with molecule coefficients and atom counts, check for each one whether both sides contain the same number of every atom type.

Level: Easy3 of 10
Topics: String, Hash map
Solved: No attempts yet

Problem

Fran did not pay attention in chemistry class, so he needs help with his homework. The homework is to check whether each of $n$ chemical equations is balanced. A chemical equation represents a chemical reaction with symbols and formulas. In a reaction, some initial molecules react to produce a new set of molecules.

An equation has a left side and a right side. The left side lists the formulas of the initial molecules, and the right side lists the product molecules. The two sides are separated by an arrow ->. Different molecules on the same side are separated by +.

Molecules are made of atoms, which are denoted by capital letters of the Latin alphabet. A molecule's formula lists the labels of all the different atoms in it. If an atom appears more than once in a molecule, its count is written after the atom label. For example, AC4B is a molecule with one atom A, four atoms C, and one atom B. If the same molecule appears more than once on one side, the number of copies is written as a coefficient in front of the formula. For example, 3AC4B means 3 molecules of AC4B, for a total of 3 atoms A, 12 atoms C, and 3 atoms B.

An equation is balanced when both sides contain the same number of atoms of each kind. Determine whether each of the $n$ equations is balanced. The equations are not necessarily balanced, but they are written correctly as described above. In all test cases, every number in a reaction (atom counts within a molecule and molecule coefficients) is a single digit and larger than 1.

Input

The first line contains a positive integer $n$ ( $1 ≤ n ≤ 10$ ), the number of equations. Each of the next $n$ lines contains one chemical equation of at most 1000 characters.

Output

For each equation, print DA if it is balanced and NE if it is not, each on its own line.

Hint

Clarification of the third example. The first equation has 4 H atoms, 2 C atoms, and 6 O atoms on both sides, so the answer is DA. The second equation has one S atom on the left and none on the right, so the answer is NE. The third equation has 5 H atoms on the left and 4 on the right, so the answer is NE. The fourth equation has 4 H atoms, 1 C atom, and 4 O atoms on both sides, so the answer is DA.

Examples3

Example 1

Input

3
A+B->AB
AB+CD->AC+DB
AB+B->AB

Expected output

DA
DA
NE

Example 2
Input
```
2
2AB+A->3AB
2AB+2AC+2BC->4ABC
```
Expected output
```
NE
DA
```

Example 3

Input

4
2H2O+2CO2->2H2CO3
H2SO4->H2O4
NH3+H2SO4->NH4SO4
CH4+2O2->CO2+2H2O

Expected output

DA
NE
NE
DA