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 號機械人）。

新造出嚟嘅機械人有三種唔同職業。對編號為 $m$ 嘅機械人，如果 $m$ 可以分解成偶數個互不相同嘅奇質數之積，佢就係政客，例如編號 $15$；否則，如果 $m$ 本身係奇質數，或者可以分解成奇數個互不相同嘅奇質數之積，佢就係軍人，例如編號 $3$、$165$。其他編號嘅機械人都係學者，例如編號 $2$、$6$、$9$。

第 $m$ 秒誕生嘅 $m$ 號機械人，想知道喺佢自己同佢嘅老師當中，所有政客嘅獨立數之和、所有軍人嘅獨立數之和，同所有學者嘅獨立數之和。不過，$m$ 號機械人忙住工作，冇時間計算，你可唔可以幫佢？

為咗方便你計算，Macsy 已經幫你將 $m$ 做咗質因數分解。為咗方便輸出，只要求輸出各個總和除以 $10000$ 嘅餘數。

輸入格式

輸入檔案 robot.in 第一行係一個正整數 $k$（$1\leq k\leq 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\leq p_i<10000$，$1\leq e_i\leq 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 分。