Pada tahun 3030, Macsy sedang menempatkan sekumpulan robot di Mars.

Pada detik pertama, ia membawa robot nomor $1$ ke Mars. Robot nomor $1$ dapat membuat robot lain.

Pada detik kedua, robot nomor $1$ membuat robot pertamanya, yaitu robot nomor $2$.

Pada detik ketiga, robot nomor $1$ membuat robot lain, yaitu robot nomor $3$.

Setelah itu, setiap detik robot nomor $1$ dapat membuat sebuah robot baru. Robot yang dibuat pada detik ke-$m$ bernomor $m$. Kita dapat menyebutnya robot nomor $m$, atau robot $m$.

Setelah dibuat, robot segera mulai bekerja. Robot nomor $m$ beristirahat setiap $m$ detik. Misalnya, robot nomor $3$ beristirahat pada detik ke-$6,9,12,\ldots$ dan bekerja pada waktu lainnya.

Ketika robot beristirahat, ingatannya ditransplantasikan ke otak robot yang lahir saat itu. Misalnya, ketika robot nomor $6$ lahir, robot nomor $2$ dan $3$ sedang beristirahat, sehingga robot nomor $6$ menerima salinan ingatan robot nomor $2$ dan $3$. Kita menyebut robot nomor $2$ dan $3$ sebagai guru robot nomor $6$.

Jika dua robot tidak memiliki hubungan guru dan murid serta tidak memiliki guru yang sama, pengetahuan kedua robot tersebut disebut saling independen. Perhatian: pengetahuan robot nomor $1$ independen dari semua robot lainnya (karena hanya robot nomor $1$ yang dapat membuat robot), dan ia bukan guru robot mana pun.

Bilangan independen suatu robot adalah banyaknya robot dengan nomor lebih kecil darinya yang pengetahuannya saling independen dengannya. Misalnya, bilangan independen robot nomor $1$ adalah $0$; bilangan independen robot nomor $2$ adalah $1$ (pengetahuan robot nomor $1$ saling independen dengannya); bilangan independen robot nomor $6$ adalah $2$ (pengetahuan robot nomor $1$ dan $5$ saling independen dengannya, robot nomor $2$ dan $3$ adalah gurunya, sedangkan robot nomor $4$ memiliki guru yang sama dengannya, yaitu robot nomor $2$).

Robot-robot baru memiliki 3 profesi berbeda. Untuk robot bernomor $m$, jika $m$ dapat diuraikan sebagai hasil kali sejumlah genap bilangan prima ganjil yang berbeda, ia adalah politikus, misalnya nomor $15$. Jika tidak, apabila $m$ sendiri merupakan bilangan prima ganjil atau dapat diuraikan sebagai hasil kali sejumlah ganjil bilangan prima ganjil yang berbeda, ia adalah tentara, misalnya nomor $3$ dan nomor $165$. Robot dengan nomor lainnya adalah ilmuwan, misalnya nomor $2$, nomor $6$, dan nomor $9$.

Robot nomor $m$ yang lahir pada detik ke-$m$ ingin mengetahui, di antara dirinya dan semua gurunya, jumlah bilangan independen semua politikus, jumlah bilangan independen semua tentara, serta jumlah bilangan independen semua ilmuwan. Namun, robot nomor $m$ sibuk bekerja dan tidak sempat menghitungnya. Dapatkah kamu membantunya?

Untuk memudahkan perhitunganmu, Macsy telah memfaktorkan $m$ menjadi faktor-faktor prima. Untuk memudahkan keluaran, kamu hanya perlu mengeluarkan sisa pembagian jumlah tersebut dengan $10000$.

Masukan

Baris pertama berkas masukan robot.in berisi sebuah bilangan bulat positif $k$ ($1 \le k \le 1000$), yaitu banyaknya faktor prima berbeda dari $m$.

Berikutnya terdapat $k$ baris, masing-masing berisi dua bilangan bulat $p_i,e_i$, yang menyatakan faktor prima ke-$i$ dari $m$ beserta pangkatnya ($i=1,2,\ldots,k$). $p_1,p_2,\ldots,p_k$ adalah bilangan prima berbeda, dan $m=\prod_{i=1}^k p_i^{e_i}$. Semua faktor prima diurutkan dari kecil ke besar, yaitu $p_1<p_2<\cdots<p_k$. Dalam berkas masukan, $2 \le p_i<10{,}000$ dan $1 \le e_i \le 1{,}000{,}000$.

Keluaran

Berkas keluaran robot.out terdiri dari tiga baris.

Baris pertama adalah sisa pembagian dengan $10000$ dari jumlah bilangan independen semua politikus di antara robot nomor $m$ dan semua gurunya.

Baris kedua adalah sisa pembagian dengan $10000$ dari jumlah bilangan independen semua tentara di antara robot nomor $m$ dan semua gurunya.

Baris ketiga adalah sisa pembagian dengan $10000$ dari jumlah bilangan independen semua ilmuwan di antara robot nomor $m$ dan semua gurunya.

Contoh

Masukan 1

3
2 1
3 2
5 1

Keluaran 1

8
6
75

Penjelasan

$m=2\times3^2\times5=90$. Robot nomor $90$ memiliki 10 guru; bersama dirinya sendiri, totalnya 11 robot. Satu-satunya politikus adalah nomor $15$; tentaranya adalah nomor $3$ dan $5$; terdapat 8 ilmuwan, yang masing-masing bernomor $2,6,9,10,18,30,45,90$.

Penilaian

Berkas keluaran berisi tiga bilangan. Jika programmu menghitung ketiganya dengan benar, nilai kasus uji tersebut adalah $10$; jika dua bilangan benar, nilainya $7$; jika satu bilangan benar, nilainya $4$; jika tidak ada bilangan yang benar, nilainya $0$.