Firma Bajtel postanowiła usprawnić produkowane przez nią komputery, przez zastąpienie zaszytych w komputerach programów assemblerowych specjalnymi układami elektronicznymi, zwanymi układami assemblerowymi. Programy assemblerowe składają się wyłącznie z przypisań. Każde przypisanie jest określone przez cztery elementy:

• dwa rejestry, z których pobierane są dane,
• operację elementarną, wykonywaną na tych danych,
• rejestr, w którym umieszczany jest wynik.

Zakładamy, że jest co najwyżej 26 rejestrów oznaczonych małymi literami alfabetu angielskiego od a do z oraz co najwyżej 4 różne operacje elementarne oznaczone wielkimi literami angielskiego alfabetu od A do D.
Układ assemblerowy ma:

• wejścia oznaczone nazwami rejestrów, na każde wejście podawana jest wartość początkowa odpowiedniego rejestru, oraz
• wyjścia oznaczone również nazwami rejestrów, których wartości końcowe są kierowane do tych rejestrów.

Wewnątrz układu znajdują się bramki. Każda bramka ma dwa wejścia i jedno wyjście. Wykonuje ona jedną operację elementarną na danych, które pojawiają się na jej wejściach i udostępnia wynik na swoim wyjściu. Wejścia bramek oraz wyjścia całego układu są połączone z wyjściami innych bramek lub wejściami układu. Wyjścia bramek oraz wejścia układu mogą być połączone z wieloma wejściami innych bramek lub wyjściami układu. Połączenia między bramkami nie tworzą cykli.

Układ assemblerowy jest równoważny programowi assemblerowemu, gdy dla dowolnego stanu początkowego rejestrów daje taki sam - jak program -stan końcowy rejestrów.

Napisz program, który:

• wczytuje z pliku tekstowego UKL.IN opis programu assemblerowego;
• oblicza najmniejszą liczbę bramek, które musi zawierać układ assemblerowy równoważny z danym programem;
• zapisuje wynik w pliku tekstowym UKL.OUT.

Wejście

W pierwszym wierszu pliku wejściowego UKL.IN znajduje się jedna liczba całkowita n (1 <= n < 1000). Jest to liczba instrukcji programu.

W n kolejnych wierszach opisane są kolejne instrukcje programu. Każdy opis ma postać czteroliterowego słowa, zaczynającego się od symbolu operacji elementarnej: A, B, C albo D. Pozostałe trzy litery są małe. Druga i trzecia - to nazwy rejestrów, z których należy pobrać dane; czwarta - to nazwa rejestru, w którym należy umieścić wynik.

Wyjście

Twój program powinien zapisać w pierwszym i jedynym wierszu pliku wyjściowego UKL.OUT jedną liczbę całkowitą - minimalną liczbę bramek układu assemblerowego, równoważnego danemu programowi.

Przykład

Dla pliku tekstowego UKL.IN:

8
Afbc
Bfbd
Cddd
Bcbc
Afcc
Afbf
Cfbb
Dfdb

poprawnym rozwiązaniem jest plik wyjściowy UKL.OUT:

6

Układ równoważny danemu programowi przedstawiono na rysunku.