En el año 3030, Macsy está desplegando un grupo de robots en Marte.
En el primer segundo transporta a Marte al robot número $1$, que puede fabricar otros robots.
En el segundo segundo, el robot $1$ fabrica su primer robot: el número $2$.
En el tercer segundo fabrica otro robot: el número $3$.
A partir de entonces, el robot $1$ puede fabricar un nuevo robot cada segundo. El robot fabricado en el segundo $m$ recibe el número $m$. Podemos llamarlo robot $m$ o robot número $m$.
En cuanto se fabrica, un robot empieza a trabajar. El robot $m$ descansa una vez cada $m$ segundos. Por ejemplo, el robot $3$ descansa en los segundos $6,9,12,\ldots$ y trabaja el resto del tiempo.
Cuando un robot descansa, su memoria se copia al cerebro del robot que nace en ese momento. Por ejemplo, cuando nace el robot $6$, los robots $2$ y $3$ están descansando, así que recibe una copia de sus memorias. Decimos que los robots $2$ y $3$ son los maestros del robot $6$.
Si dos robots no tienen una relación de maestro y alumno ni un maestro común, decimos que sus conocimientos son independientes. Atención: los conocimientos del robot $1$ son independientes de los de todos los demás (porque solo él puede fabricar robots), y no es maestro de ningún robot.
El número de independencia de un robot es la cantidad de robots con un número menor que el suyo cuyos conocimientos son independientes de los suyos. Por ejemplo, el número de independencia del robot $1$ es $0$; el del robot $2$ es $1$ (sus conocimientos son independientes de los del robot $1$); y el del robot $6$ es $2$ (es independiente de los robots $1$ y $5$; los robots $2$ y $3$ son sus maestros, y el robot $4$ comparte con él un maestro: el robot $2$).
Los robots recién fabricados tienen tres profesiones posibles. Si el número $m$ de un robot se puede expresar como el producto de una cantidad par de primos impares distintos, es político, como el robot $15$. En caso contrario, si $m$ es un primo impar o se puede expresar como el producto de una cantidad impar de primos impares distintos, es militar, como los robots $3$ y $165$. Los robots con los demás números son académicos, como los robots $2$, $6$ y $9$.
El robot $m$, nacido en el segundo $m$, quiere conocer, entre él mismo y sus maestros, la suma de los números de independencia de todos los políticos, la de todos los militares y la de todos los académicos. Pero está demasiado ocupado trabajando para calcularlas. ¿Puedes ayudarlo?
Para facilitarte el cálculo, Macsy ya ha factorizado $m$ en primos. Para facilitar la salida, solo se piden los restos de las sumas al dividirlas entre $10000$.
Entrada
La primera línea del archivo de entrada robot.in contiene un entero positivo $k$ ($1\le k\le 1000$), que es el número de factores primos distintos de $m$.
Cada una de las siguientes $k$ líneas contiene dos enteros $p_i,e_i$, que representan el factor primo $i$ de $m$ y su exponente ($i=1,2,\ldots,k$). Los valores $p_1,p_2,\ldots,p_k$ son primos distintos y $m=\prod_{i=1}^k p_i^{e_i}$. Los factores primos están ordenados de menor a mayor, es decir, $p_1<p_2<\cdots<p_k$. En la entrada se cumple $2\le p_i<10000$, $1\le e_i\le 1000000$.
Salida
El archivo de salida robot.out contiene tres líneas.
La primera línea contiene el resto, al dividir entre $10000$, de la suma de los números de independencia de todos los políticos entre el robot $m$ y sus maestros.
La segunda línea contiene el resto, al dividir entre $10000$, de la suma de los números de independencia de todos los militares entre el robot $m$ y sus maestros.
La tercera línea contiene el resto, al dividir entre $10000$, de la suma de los números de independencia de todos los académicos entre el robot $m$ y sus maestros.
Ejemplos
Entrada 1
3 2 1 3 2 5 1
Salida 1
8 6 75
Nota
$m=2\times 3^2\times 5=90$. El robot $90$ tiene 10 maestros, así que son 11 robots contando al propio robot $90$. El único político es el robot $15$; los militares son los robots $3$ y $5$; y hay 8 académicos, con los números $2,6,9,10,18,30,45,90$.
Subtareas
El archivo de salida contiene tres números. Si tu programa calcula correctamente los tres, obtiene 10 puntos en ese caso de prueba; si calcula correctamente dos, obtiene 7 puntos; si calcula correctamente uno, obtiene 4 puntos; y si no calcula correctamente ninguno, obtiene 0 puntos.