Problem description

Pewnego dnia Pomysłowy Dobromir postanowił skonstruować nowy wynalazek – maszynę do robienia tęczy! Wszystko było już prawie gotowe: zębatki się kręciły, woda pryskała, a promienie słońca odbijały się od lusterek. Niestety, aby maszyna mogła zadziałać, Dobromirowi brakowało jednego składnika - musiał użyć tajemniczego eliksiru tęczy, którego recepturę znalazł w starym zeszycie od chemii.

– Ach, te reakcje chemiczne! – westchnął Dobromir, wpatrując się w równania zapisane w zeszycie. – Muszę sprawdzić, czy te równania są zrównoważone, bo inaczej zamiast tęczy będzie tu zwykła mgiełka!

Z zapałem zaczął liczyć atomy w każdej formule – lewa strona, strzałka, prawa strona i znowu to samo. Dobromir pochylił się nad zeszytem, podrapał się po rudej czuprynie. Żaróweczka pojawiła się nad głową, jednak nie rozbłysła światłem. Dobromir nie był najlepszy w rachunkach – w końcu większość czasu spędzał na majsterkowaniu, a nie na nauce chemii.

I nagle - spojrzenie Dobromira z zeszytu przeniosło się w stronę kamery – może ktoś, kto ma więcej doświadczenia w liczeniu, pomoże mu rozwiązać tę zagadkę? Żaróweczka rozświetliła się. Tak oto Dobromir postanowił zwrócić się o pomoc do Ciebie! Rozwiąż problem Dobromira sprawdzając, czy równania chemiczne są zrównoważone, aby maszyna mogła w końcu stworzyć tęczę!

Zadanie Dobromira składa się z N równań reakcji chemicznych. Dla każdego z nich należy sprawdzić, czy jest ono zrównoważone. Równanie chemiczne jest symbolicznym zapisem przebiegu reakcji. W reakcji chemicznej pewien zestaw początkowych cząsteczek (substraty) reaguje, tworząc nowy zestaw cząsteczek (produkty).

Każde równanie składa się z lewej i prawej strony. Lewa strona zawiera wzory chemiczne substratów, natomiast prawa zawiera wzory produktów. Lewa i prawa strona równania są oddzielone strzałką (znakiem ->). Różne cząsteczki pojawiające się po lewej lub prawej stronie są rozdzielone znakiem +.

Cząsteczki zbudowane są z atomów (połączonych wiązaniem) oznaczonych wielkimi literami alfabetu łacińskiego (na potrzeby tego zadania). Wzór cząsteczki określają wszystkie występujące w nim atomy. Jeśli cząsteczka ma wiele wystąpień danego atomu, to ich liczba zapisywana jest po symbolu atomu. Na przykład AC4B to wzór cząsteczki, która ma jeden atom A, 4 atomy C i jeden atom B.

Jeśli po jednej stronie równania cząsteczka pojawia się więcej niż raz, liczba tych cząsteczek jest zapisana jako współczynnik przed wzorem. Na przykład 3AC4B oznacza 3 cząsteczki AC4B, co daje w sumie 3 atomy A, 12 atomów C i 3 atomy B.

Równanie chemiczne uważa się za zrównoważone, jeśli prawa i lewa strona zawierają równą liczbę atomów każdego rodzaju. Twoim zadaniem jest określić, czy każde z N równań chemicznych jest zrównoważone.

Wszystkie współczynniki przed cząsteczkami oraz za atomami są pojedynczymi cyframi.

Wejście

W pierwszym wierszu wejścia znajduje się liczba N - liczba reakcji chemicznych. W kolejnych N wierszach wejścia znajdują się ciągi liter (każdy o długości  ≤ 1000 znaków), określające równania reakcji chemicznych - po lewej stronie strzałki znajdują się substraty, po prawej produkty.

Wyjście

W N wierszach wyjścia należy wypisać TAK - jeśli równianie jest zrównoważone, albo NIE - jeśli nie jest.

Ograniczenia

1 ≤ N ≤ 100.

Każdy wiersz ma długość  ≤ 1000 znaków.

Część punktów otrzymasz za rozwiązanie zadania dla równań, w których:
1. Nie ma współczynników i wszystkie cząsteczki są atomami,
2. Wszystkie cząsteczki są atomami.

Przykład

2
H2+O2->H2O
2H2+O2->2H2O

NIE
TAK

5
2CH+3O2->2CO+H2O
2AO3C2+4AD->2CO2+4O2A+2D
BO2+H2SO4->BSO4+H2O2
H2O2->H2O+O
2CA+O2->2CO

NIE
NIE
TAK
TAK
NIE