Alternatywne formaty: PostScript | PDF

Bajtocki Bank Bitowy (w skrócie BBB) ma największą w Bajtocji sieć bankomatów. Klienci BBB wypłacają pieniądze z bankomatów na podstawie karty bankomatowej i 4-cyfrowego kodu PIN. Niedawno, w celu zwiększenia bezpieczeństwa swoich klientów, BBB zainstalował przy każdym bankomacie kamerę. Kamery przesyłają rejestrowany obraz do BBB drogą radiową. Niestety, sygnał wysyłany przez kamery jest przechwytywany przez szajkę złodziejaszków komputerowych. Złodziejaszkowie starają się odkryć 4-cyfrowe kody PIN klientów BBB, którym następnie kradną karty bankomatowe. Wiedząc o tym, klienci BBB, wprowadzając PIN i przesuwając palec nad klawiaturą, starają się wykonywać nadmiarowe ruchy. Kamera nie jest w stanie wychwycić naciskania klawiszy, rejestruje jedynie przesunięcia palca. Tak więc, jednoznaczne wyznaczenie wprowadzanego kodu PIN jest zazwyczaj niemożliwe. Przykładowo, klient przesuwający swój palec najpierw nad klawiszem 1, a potem 5, mógł wprowadzić następujące kody PIN: 1111, 1115, 1155, 1555 lub 5555. Zdesperowani złodziejaszkowie gromadzą nagrania z kamer, licząc na to, że być może na podstawie wielu nagrań tego samego klienta będą w stanie wyznaczyć wprowadzany przez niego PIN, lub choćby ograniczyć liczbę możliwych kodów. Zebrawszy sekwencje wprowadzane przez pewnego bogatego klienta BBB, złożyli Ci propozycję "nie do odrzucenia".

Zadanie

Napisz program, który:

• wczyta ze standardowego wejścia opis zarejestrowanych sekwencji ruchów palca, jakie klient banku wykonywał wprowadzając swój PIN,
• wyznaczy liczbę różnych kodów PIN, jakie może mieć klient (czyli liczbę tych 4-cyfrowych kodów PIN, które mogły być wprowadzone do bankomatu przy wykonywaniu zadanych sekwencji ruchów palca),
• wypisze znalezione rozwiązanie na standardowe wyjście.

Wejście

Pierwszy wiersz wejścia zawiera jedną dodatnią liczbę całkowitą n równą liczbie zarejestrowanych scen wprowadzania kodu PIN przez klienta, 1 <= n <= 1000. W kolejnych n wierszach znajdują się opisy tych scen, po jednej w wierszu. Opis każdej sceny składa się z dwóch dodatnich liczb całkowitych oddzielonych pojedynczym odstępem. Pierwsza z tych liczb, t, to długość sekwencji ruchów, 1 <= t <= 10.000. Druga z tych liczb to t-cyfrowa liczba, której kolejne cyfry reprezentują kolejne klawisze, nad którymi klient przesuwał palec. Łączna długość wszystkich sekwencji nie przekracza 1.000.000.

Wyjście

W pierwszym i jedynym wierszu wyjścia powinna znaleźć się jedna dodatnia liczba całkowita równa liczbie możliwych kodów PIN klienta.

Przykład

Dla danych wejściowych:

2
3 123
3 234

prawidłową odpowiedzią jest:

5

Wersja do druku