En 3030, Macsy déploie un groupe de robots sur Mars.

À la première seconde, il amène sur Mars le robot numéro 1, capable de fabriquer d'autres robots.

À la deuxième seconde, le robot 1 fabrique son premier robot : le robot 2.

À la troisième seconde, il fabrique un autre robot : le robot 3.

Puis, à chaque seconde, le robot 1 peut fabriquer un nouveau robot. Celui fabriqué à la $m$-ième seconde porte le numéro $m$. On l'appelle le robot numéro $m$, ou le $m$-ième robot.

Un robot commence à travailler dès sa fabrication. Le robot $m$ se repose une fois toutes les $m$ secondes. Par exemple, le robot 3 se repose aux secondes $6,9,12,\dots$ et travaille le reste du temps.

Lorsqu'un robot se repose, sa mémoire est transplantée dans le cerveau du robot qui naît à cet instant. Par exemple, lorsque le robot 6 naît, les robots 2 et 3 se reposent. Le robot 6 reçoit donc des copies de leurs mémoires. On appelle les robots 2 et 3 les enseignants du robot 6.

Si deux robots n'ont pas de relation enseignant-élève et n'ont aucun enseignant commun, leurs connaissances sont dites indépendantes. Attention : les connaissances du robot 1 sont indépendantes de celles de tous les autres robots (car lui seul sait fabriquer des robots), et il n'est l'enseignant d'aucun robot.

Le nombre d'indépendance d'un robot est le nombre de robots de numéro inférieur au sien dont les connaissances sont indépendantes des siennes. Par exemple, celui du robot 1 vaut 0 ; celui du robot 2 vaut 1 (le robot 1 est indépendant de lui) ; celui du robot 6 vaut 2 (les robots 1 et 5 sont indépendants de lui ; les robots 2 et 3 sont ses enseignants, et le robot 4 partage avec lui un enseignant : le robot 2).

Les nouveaux robots exercent trois professions différentes. Pour un robot de numéro $m$, si $m$ peut être décomposé en un produit d'un nombre pair de nombres premiers impairs distincts, il est politicien, comme le robot 15. Sinon, si $m$ est lui-même un nombre premier impair ou peut être décomposé en un produit d'un nombre impair de nombres premiers impairs distincts, il est militaire, comme les robots 3 et 165. Tous les autres robots sont savants, comme les robots 2, 6 et 9.

Le robot $m$, né à la $m$-ième seconde, souhaite connaître, parmi lui-même et ses enseignants, la somme des nombres d'indépendance de tous les politiciens, celle de tous les militaires et celle de tous les savants. Mais il est trop occupé à travailler pour les calculer. Pouvez-vous l'aider ?

Pour faciliter vos calculs, Macsy a déjà décomposé $m$ en facteurs premiers. Pour simplifier la sortie, vous devez uniquement afficher les restes de ces sommes dans la division par $10000$.

Entrée

La première ligne du fichier robot.in contient un entier positif $k$ ($1\le k\le1000$), le nombre de facteurs premiers distincts de $m$.

Chacune des $k$ lignes suivantes contient deux entiers $p_i,e_i$, le $i$-ième facteur premier de $m$ et son exposant ($i=1,2,\dots,k$). Les nombres $p_1,p_2,\dots,p_k$ sont premiers et distincts, et $m=\prod_{i=1}^{k}p_i^{e_i}$. Ils sont donnés par ordre croissant : $p_1<p_2<\dots<p_k$. Dans le fichier d'entrée, $2\le p_i<10000$, $1\le e_i\le1000000$.

Sortie

Le fichier robot.out comporte trois lignes.

La première contient le reste modulo $10000$ de la somme des nombres d'indépendance des politiciens parmi le robot $m$ et ses enseignants.

La deuxième contient le reste modulo $10000$ de la somme des nombres d'indépendance des militaires parmi le robot $m$ et ses enseignants.

La troisième contient le reste modulo $10000$ de la somme des nombres d'indépendance des savants parmi le robot $m$ et ses enseignants.

Exemples

Entrée 1

3
2 1
3 2
5 1

Sortie 1

8
6
75

Remarque

$m=2\times3^2\times5=90$. Le robot 90 possède 10 enseignants ; en le comptant lui-même, cela fait 11 robots. Le seul politicien est le robot 15 ; les militaires sont les robots 3 et 5 ; il y a 8 savants, dont les numéros sont $2,6,9,10,18,30,45,90$.

Sous-tâches

Le fichier de sortie contient trois nombres. Si votre programme calcule correctement les trois, vous obtenez 10 points pour le test ; s'il en calcule correctement deux, vous obtenez 7 points ; s'il en calcule correctement un, vous obtenez 4 points ; s'il n'en calcule aucun correctement, vous obtenez 0 point.