Segalt

O pereche de șiruri de caractere $S$ și $T$, formate doar din literele A, B și C, este egalabilă dacă șirurile pot deveni egale după o transfomare constând din aplicarea unei succesiuni formate din $0$ sau mai multe operații. O operație constă din inserarea sau ștergerea din unul dintre șiruri a uneia dintre subsecvențele: AAA, BBB, CCC, ABC sau BAC. Atât inserarea, cât și ștergerea se pot realiza de pe orice poziție. În urma unei operații este posibil ca șirul rezultat să devină vid.

Cerință

Pentru o succesiune dată de perechi de șiruri, să se determine, pentru fiecare pereche, dacă este egalabilă.

Date de intrare

Fișierul de intrare segalt.in conține pe prima linie numărul $Q$ de perechi. Pentru fiecare pereche sunt specificate cele două șiruri, pe linii diferite.

Date de ieșire

Fișierul de ieșire segalt.out va conține $Q$ linii. Pe cea de a $i$-a linie va fi scris mesajul DA dacă cea de a $i$-a pereche din fișierul de intrare este egalabilă, respectiv mesajul NU, în caz contrar.

Restricții și precizări

• $1 \leq Q \leq 10 \ 000$
• $1 \leq$ lungimea maximă a unui șir (notată cu $N_{max}$) $\leq 175 \ 000$
• Suma lungimilor șirurilor din toate perechile (notată cu $S$) este cel mult $350 \ 000$

Exemplu

segalt.in

2
ABC
CCC
AABBACCBCCBC
CCCCCCCCC

segalt.out

DA
NU

Explicație

Pentru prima pereche secvența ABC din primul șir poate fi ștearsă, apoi se inserează secvența CCC.
Pentru a doua pereche se poate demonstra că nu există nicio transformare în urma căreia șirurile să devină egale.