W roku 3030 Macsy rozmieszcza na Marsie grupę robotów.

W pierwszej sekundzie dostarczył na Marsa robota numer $1$, który potrafi wytwarzać inne roboty.

W drugiej sekundzie robot numer $1$ stworzył pierwszego robota — robota numer $2$.

W trzeciej sekundzie robot numer $1$ stworzył kolejnego robota — robota numer $3$.

W każdej następnej sekundzie robot numer $1$ może stworzyć nowego robota. Robot stworzony w sekundzie $m$ ma numer $m$. Możemy nazywać go robotem numer $m$ lub $m$-tym robotem.

Robot zaczyna pracować natychmiast po powstaniu. Robot numer $m$ odpoczywa co $m$ sekund. Na przykład robot numer $3$ odpoczywa w sekundach $6,9,12,\ldots$, a w pozostałym czasie pracuje.

Kiedy robot odpoczywa, jego pamięć zostaje przeniesiona do mózgu robota, który właśnie powstaje. Na przykład w chwili powstania robota numer $6$ roboty numer $2$ i $3$ odpoczywają, więc robot numer $6$ otrzymuje kopie ich pamięci. Roboty numer $2$ i $3$ nazywamy nauczycielami robota numer $6$.

Jeśli dwa roboty nie pozostają w relacji nauczyciel–uczeń i nie mają wspólnego nauczyciela, ich wiedzę nazywamy niezależną. Uwaga: wiedza robota numer $1$ jest niezależna od wiedzy wszystkich pozostałych robotów (ponieważ tylko on potrafi tworzyć roboty); nie jest on również nauczycielem żadnego robota.

Liczba niezależności robota to liczba robotów o mniejszych numerach, których wiedza jest niezależna od jego wiedzy. Na przykład liczba niezależności robota numer $1$ wynosi $0$, robota numer $2$ wynosi $1$ (robot numer $1$ ma wiedzę niezależną od jego wiedzy), a robota numer $6$ wynosi $2$ (roboty numer $1$ i $5$ mają wiedzę niezależną od jego wiedzy; roboty numer $2$ i $3$ są jego nauczycielami, a robot numer $4$ ma z nim wspólnego nauczyciela — robota numer $2$).

Nowo powstałe roboty wykonują jeden z trzech zawodów. Robot numer $m$ jest politykiem, jeśli $m$ można rozłożyć na iloczyn parzystej liczby różnych nieparzystych liczb pierwszych, na przykład robot numer $15$. W przeciwnym razie, jeśli samo $m$ jest nieparzystą liczbą pierwszą lub można je rozłożyć na iloczyn nieparzystej liczby różnych nieparzystych liczb pierwszych, robot jest żołnierzem, jak roboty numer $3$ i $165$. Wszystkie pozostałe roboty są uczonymi, na przykład roboty numer $2$, $6$ i $9$.

Robot numer $m$, powstały w sekundzie $m$, chce znać sumę liczb niezależności wszystkich polityków, sumę liczb niezależności wszystkich żołnierzy oraz sumę liczb niezależności wszystkich uczonych wśród siebie i swoich nauczycieli. Jest jednak zbyt zajęty pracą, by to obliczyć. Czy możesz mu pomóc?

Aby ułatwić obliczenia, Macsy rozłożył już $m$ na czynniki pierwsze. Dla wygody wystarczy wypisać reszty z dzielenia sum przez $10000$.

Wejście

Pierwszy wiersz pliku robot.in zawiera dodatnią liczbę całkowitą $k$ ($1\le k\le1000$), oznaczającą liczbę różnych czynników pierwszych $m$.

Każdy z następnych $k$ wierszy zawiera dwie liczby całkowite $p_i,e_i$: $i$-ty czynnik pierwszy $m$ i jego wykładnik ($i=1,2,\ldots,k$). Liczby $p_1,p_2,\ldots,p_k$ są różnymi liczbami pierwszymi, a $m=\prod_{i=1}^{k}p_i^{e_i}$. Czynniki są podane rosnąco: $p_1<p_2<\cdots<p_k$. Zachodzi $2\le p_i<10\,000$ oraz $1\le e_i\le1\,000\,000$.

Wyjście

Plik robot.out zawiera trzy wiersze.

Pierwszy wiersz zawiera resztę z dzielenia przez $10000$ sumy liczb niezależności wszystkich polityków wśród robota numer $m$ i jego nauczycieli.

Drugi wiersz zawiera resztę z dzielenia przez $10000$ sumy liczb niezależności wszystkich żołnierzy wśród robota numer $m$ i jego nauczycieli.

Trzeci wiersz zawiera resztę z dzielenia przez $10000$ sumy liczb niezależności wszystkich uczonych wśród robota numer $m$ i jego nauczycieli.

Przykład

Wejście 1

3
2 1
3 2
5 1

Wyjście 1

8
6
75

Uwagi

$m=2\times3^2\times5=90$. Robot numer $90$ ma $10$ nauczycieli, więc razem z nim jest $11$ robotów. Jedynym politykiem jest robot numer $15$; żołnierzami są roboty numer $3$ i $5$; uczonych jest $8$, a ich numery to $2,6,9,10,18,30,45,90$.

Podzadania

Plik wyjściowy zawiera trzy liczby. Jeśli program obliczy poprawnie wszystkie trzy, otrzymuje $10$ punktów za test; za dwie poprawne liczby otrzymuje $7$ punktów; za jedną poprawną liczbę otrzymuje $4$ punkty; jeśli żadna liczba nie jest poprawna, otrzymuje $0$ punktów.