3030 年，Macsy 正在火星部署一批機器人。

第 1 秒，他把機器人 1 號運到了火星，機器人 1 號可以製造其他的機器人。

第 2 秒，機器人 1 號造出了第一個機器人——機器人 2 號。

第 3 秒，機器人 1 號造出了另一個機器人——機器人 3 號。

之後每一秒，機器人 1 號都可以造出一個新的機器人。第 $m$ 秒造出的機器人編號為 $m$。我們可以稱它為機器人 $m$ 號，或者 $m$ 號機器人。

機器人造出來後，馬上開始工作。$m$ 號機器人，每 $m$ 秒會休息一次。比如 3 號機器人，會在第 $6,9,12,\ldots$ 秒休息，而其他時間都在工作。

機器人休息時，它的記憶將會被移植到當時出生的機器人的腦中。比如 6 號機器人出生時，2、3 號機器人正在休息，因此，6 號機器人會收到第 2、3 號機器人的記憶副本。我們稱第 2、3 號機器人是 6 號機器人的老師。

如果兩個機器人沒有師徒關係，且沒有共同的老師，則稱這兩個機器人的知識是互相獨立的。注意：1 號機器人與其他所有機器人的知識獨立（因為只有 1 號才會造機器人），它也不是任何機器人的老師。

一個機器人的獨立數，是指所有編號比它小且與它知識互相獨立的機器人的個數。比如 1 號機器人的獨立數為 $0$，2 號機器人的獨立數為 $1$（1 號機器人與它知識互相獨立），6 號機器人的獨立數為 $2$（1、5 號機器人與它知識互相獨立，2、3 號機器人都是它的老師，而 4 號機器人與它有共同的老師——2 號機器人）。

新造出來的機器人有 3 種不同的職業。對於編號為 $m$ 的機器人，如果能把 $m$ 分解成偶數個不同奇質數的積，則它是政客，例如編號 $15$；否則，如果 $m$ 本身就是奇質數或者能把 $m$ 分解成奇數個不同奇質數的積，則它是軍人，例如編號 $3$、編號 $165$。其他編號的機器人都是學者，例如編號 $2$、編號 $6$、編號 $9$。

第 $m$ 秒誕生的機器人 $m$ 號，想知道它和它的老師中，所有政客的獨立數之和、所有軍人的獨立數之和，以及所有學者的獨立數之和。可機器人 $m$ 號忙於工作沒時間計算，你能夠幫助它嗎？

為了方便你的計算，Macsy 已經幫你做了 $m$ 的質因數分解。為了輸出方便，只要求輸出總和對 $10000$ 取模的結果。

輸入格式

輸入檔案 robot.in 的第一行是一個正整數 $k$（$1\le k\le 1000$），$k$ 是 $m$ 的不同的質因數個數。

以下 $k$ 行，每行兩個整數 $p_i,e_i$，表示 $m$ 的第 $i$ 個質因數和它的指數（$i=1,2,\ldots,k$）。$p_1,p_2,\ldots,p_k$ 是不同的質數，$m=\prod_{i=1}^{k}p_i^{e_i}$。所有質因數按照從小到大排列，即 $p_1<p_2<\cdots<p_k$。輸入檔案中，$2\le p_i<10000$，$1\le e_i\le 1000000$。

輸出格式

輸出檔案 robot.out 包括三行。

第一行是機器人 $m$ 號和它的老師中，所有政客的獨立數之和對 $10000$ 取模的結果。

第二行是機器人 $m$ 號和它的老師中，所有軍人的獨立數之和對 $10000$ 取模的結果。

第三行是機器人 $m$ 號和它的老師中，所有學者的獨立數之和對 $10000$ 取模的結果。

範例

輸入格式 1

3
2  1
3  2
5  1

輸出格式 1

8
6
75

說明

$m=2\times 3^2\times 5=90$。90 號機器人有 10 個老師，加上它自己共 11 個。其中政客只有 15 號；軍人有 3 號和 5 號；學者有 8 個，它們的編號分別是：$2,6,9,10,18,30,45,90$。

子任務

輸出檔案包含三個數。如果你的程式算對了三個數，該測試點得 10 分；如果你的程式算對了兩個數，該測試點得 7 分；如果你的程式算對了一個數，該測試點得 4 分；如果你的程式一個數也沒算對，該測試點得 0 分。