No ano de 3030, Macsy está a colocar um grupo de robôs em Marte.

No primeiro segundo, levou para Marte o robô número 1, que pode fabricar outros robôs.

No segundo segundo, o robô 1 fabricou o primeiro robô: o robô número 2.

No terceiro segundo, o robô 1 fabricou outro robô: o robô número 3.

A partir daí, em cada segundo, o robô 1 pode fabricar um novo robô. O robô fabricado no segundo $m$ tem o número $m$. Podemos chamar-lhe robô número $m$, ou robô $m$.

Assim que é fabricado, um robô começa imediatamente a trabalhar. O robô $m$ descansa uma vez a cada $m$ segundos. Por exemplo, o robô 3 descansa nos segundos $6,9,12,\ldots$ e trabalha em todos os outros instantes.

Quando um robô descansa, a sua memória é implantada no cérebro do robô que nasce nesse instante. Por exemplo, quando nasce o robô 6, os robôs 2 e 3 estão a descansar, pelo que o robô 6 recebe cópias das suas memórias. Dizemos que os robôs 2 e 3 são os professores do robô 6.

Se dois robôs não tiverem uma relação de professor e aluno nem professores em comum, dizemos que os seus conhecimentos são independentes. Atenção: o conhecimento do robô 1 é independente do de todos os outros robôs, pois só ele fabrica robôs, e ele não é professor de nenhum robô.

O número de independência de um robô é a quantidade de robôs com número inferior ao seu cujos conhecimentos são independentes dos seus. Por exemplo, o número de independência do robô 1 é $0$; o do robô 2 é $1$, pois o robô 1 tem conhecimento independente do seu; e o do robô 6 é $2$, pois os robôs 1 e 5 têm conhecimentos independentes dos seus, os robôs 2 e 3 são seus professores, e o robô 4 tem com ele um professor em comum: o robô 2.

Os robôs recém-fabricados têm três profissões diferentes. Se o número $m$ de um robô puder ser decomposto num produto de uma quantidade par de números primos ímpares distintos, o robô é político, como o robô 15. Caso contrário, se $m$ for um primo ímpar ou puder ser decomposto num produto de uma quantidade ímpar de números primos ímpares distintos, é militar, como os robôs 3 e 165. Todos os outros robôs são estudiosos, como os robôs 2, 6 e 9.

O robô $m$, que nasce no segundo $m$, quer saber, entre ele e os seus professores, a soma dos números de independência de todos os políticos, a soma dos números de independência de todos os militares e a soma dos números de independência de todos os estudiosos. Porém, está demasiado ocupado a trabalhar para fazer as contas. Podes ajudá-lo?

Para facilitar o cálculo, Macsy já fatorizou $m$ em fatores primos. Para facilitar a saída, só é necessário apresentar os restos das somas na divisão por $10000$.

Entrada

A primeira linha do ficheiro de entrada robot.in contém um inteiro positivo $k$, com $1\le k\le1000$, que é o número de fatores primos distintos de $m$.

Seguem-se $k$ linhas. Cada uma contém dois inteiros $p_i,e_i$, que representam o $i$-ésimo fator primo de $m$ e o seu expoente, para $i=1,2,\ldots,k$. Os números $p_1,p_2,\ldots,p_k$ são primos distintos, e $m=\prod_{i=1}^k p_i^{e_i}$. Todos os fatores primos são dados por ordem crescente: $p_1<p_2<\cdots<p_k$. Na entrada, $2\le p_i<10000$ e $1\le e_i\le1000000$.

Saída

O ficheiro de saída robot.out contém três linhas.

A primeira linha é o resto, na divisão por $10000$, da soma dos números de independência de todos os políticos entre o robô $m$ e os seus professores.

A segunda linha é o resto, na divisão por $10000$, da soma dos números de independência de todos os militares entre o robô $m$ e os seus professores.

A terceira linha é o resto, na divisão por $10000$, da soma dos números de independência de todos os estudiosos entre o robô $m$ e os seus professores.

Exemplos

Entrada 1

3
2  1
3  2
5  1

Saída 1

8
6
75

Nota

$m=2\times3^2\times5=90$. O robô 90 tem 10 professores; incluindo ele próprio, são 11 robôs. Há apenas um político, o robô 15; os militares são os robôs 3 e 5; e há 8 estudiosos, com os números $2,6,9,10,18,30,45,90$.

Critérios de avaliação

O ficheiro de saída contém três números. Se o teu programa calcular corretamente os três, obtém 10 pontos nesse teste; se calcular corretamente dois, obtém 7 pontos; se calcular corretamente um, obtém 4 pontos; e se não calcular corretamente nenhum, obtém 0 pontos.