Im Jahr 3030 setzt Macsy eine Gruppe von Robotern auf dem Mars ein.

In der 1. Sekunde bringt er Roboter 1 auf den Mars. Roboter 1 kann weitere Roboter herstellen.

In der 2. Sekunde stellt Roboter 1 seinen ersten Roboter her: Roboter 2.

In der 3. Sekunde stellt Roboter 1 einen weiteren Roboter her: Roboter 3.

Danach kann Roboter 1 in jeder Sekunde einen neuen Roboter herstellen. Der in der $m$-ten Sekunde hergestellte Roboter trägt die Nummer $m$. Wir nennen ihn Roboter $m$ oder den $m$-ten Roboter.

Sobald ein Roboter hergestellt ist, beginnt er zu arbeiten. Roboter $m$ macht alle $m$ Sekunden eine Pause. Beispielsweise pausiert Roboter 3 in der 6., 9., 12., … Sekunde und arbeitet zu allen anderen Zeiten.

Wenn ein Roboter pausiert, wird sein Gedächtnis in das Gehirn des gerade entstehenden Roboters übertragen. Beispielsweise pausieren bei der Entstehung von Roboter 6 die Roboter 2 und 3. Daher erhält Roboter 6 Kopien ihrer Gedächtnisse. Wir nennen die Roboter 2 und 3 die Lehrer von Roboter 6.

Zwei Roboter haben voneinander unabhängiges Wissen, wenn keiner der Lehrer des anderen ist und sie keinen gemeinsamen Lehrer haben. Beachte: Roboter 1 hat von allen anderen Robotern unabhängiges Wissen, weil nur er Roboter herstellen kann. Er ist auch kein Lehrer irgendeines Roboters.

Die Unabhängigkeitszahl eines Roboters ist die Anzahl der Roboter mit kleinerer Nummer, deren Wissen von seinem unabhängig ist. Beispielsweise hat Roboter 1 die Unabhängigkeitszahl $0$. Roboter 2 hat die Unabhängigkeitszahl $1$, da Roboter 1 von ihm unabhängiges Wissen hat. Roboter 6 hat die Unabhängigkeitszahl $2$: Die Roboter 1 und 5 haben von ihm unabhängiges Wissen. Die Roboter 2 und 3 sind seine Lehrer, und Roboter 4 hat mit ihm einen gemeinsamen Lehrer, nämlich Roboter 2.

Neu hergestellte Roboter haben drei verschiedene Berufe. Lässt sich die Nummer $m$ eines Roboters als Produkt einer geraden Anzahl verschiedener ungerader Primzahlen darstellen, ist er Politiker, beispielsweise Roboter 15. Andernfalls ist er Soldat, wenn $m$ selbst eine ungerade Primzahl ist oder sich als Produkt einer ungeraden Anzahl verschiedener ungerader Primzahlen darstellen lässt, beispielsweise die Roboter 3 und 165. Alle übrigen Roboter sind Gelehrte, beispielsweise die Roboter 2, 6 und 9.

Roboter $m$, der in der $m$-ten Sekunde entsteht, möchte für die Menge aus ihm selbst und seinen Lehrern drei Summen kennen: die Summe der Unabhängigkeitszahlen aller Politiker, die aller Soldaten und die aller Gelehrten. Doch er ist zu beschäftigt mit seiner Arbeit, um sie zu berechnen. Kannst du ihm helfen?

Um dir die Berechnung zu erleichtern, hat Macsy $m$ bereits in Primfaktoren zerlegt. Für eine bequemere Ausgabe musst du nur die Reste der Summen bei Division durch $10000$ ausgeben.

Eingabe

Die erste Zeile der Eingabedatei robot.in enthält eine positive ganze Zahl $k$ mit $1\le k\le 1000$, die Anzahl der verschiedenen Primfaktoren von $m$.

Es folgen $k$ Zeilen mit jeweils zwei ganzen Zahlen $p_i,e_i$, dem $i$-ten Primfaktor von $m$ und seinem Exponenten für $i=1,2,\ldots,k$. Die Zahlen $p_1,p_2,\ldots,p_k$ sind verschiedene Primzahlen, und es gilt $m=\prod_{i=1}^{k}p_i^{e_i}$. Alle Primfaktoren stehen in aufsteigender Reihenfolge, also $p_1<p_2<\cdots<p_k$. Für die Eingabe gilt $2\le p_i<10000$, $1\le e_i\le 1000000$.

Ausgabe

Die Ausgabedatei robot.out besteht aus drei Zeilen.

Die erste Zeile enthält den Rest bei Division durch $10000$ der Summe der Unabhängigkeitszahlen aller Politiker unter Roboter $m$ und seinen Lehrern.

Die zweite Zeile enthält den Rest bei Division durch $10000$ der Summe der Unabhängigkeitszahlen aller Soldaten unter Roboter $m$ und seinen Lehrern.

Die dritte Zeile enthält den Rest bei Division durch $10000$ der Summe der Unabhängigkeitszahlen aller Gelehrten unter Roboter $m$ und seinen Lehrern.

Beispiele

Eingabe 1

3
2 1
3 2
5 1

Ausgabe 1

8
6
75

Hinweis

Es gilt $m=2\times 3^2\times 5=90$. Roboter 90 hat 10 Lehrer; mit ihm selbst sind es insgesamt 11 Roboter. Der einzige Politiker ist Roboter 15. Soldaten sind die Roboter 3 und 5. Es gibt 8 Gelehrte mit den Nummern $2,6,9,10,18,30,45,90$.

Teilaufgaben

Die Ausgabedatei enthält drei Zahlen. Berechnet dein Programm alle drei richtig, erhältst du 10 Punkte für den Testfall. Bei zwei richtigen Zahlen erhältst du 7 Punkte, bei einer richtigen Zahl 4 Punkte und bei keiner richtigen Zahl 0 Punkte.