3030 年、Macsy は火星にロボットを配備しています。

1 秒目に、他のロボットを製造できるロボット 1 号を火星へ運びました。

2 秒目に、1 号は最初のロボットである 2 号を製造しました。

3 秒目に、1 号はもう 1 台、3 号を製造しました。

それ以降も毎秒、1 号は新しいロボットを 1 台製造できます。$m$ 秒目に製造されたロボットの番号は $m$ で、ロボット $m$ 号、あるいは $m$ 号ロボットと呼びます。

製造されたロボットはすぐに働き始めます。$m$ 号は $m$ 秒ごとに 1 回休憩します。例えば、3 号は $6,9,12,\ldots$ 秒目に休憩し、それ以外は働きます。

ロボットが休憩すると、その記憶が、その時刻に生まれたロボットの頭脳に移植されます。例えば、6 号が生まれるときには 2 号と 3 号が休憩しているため、6 号は 2 号と 3 号の記憶のコピーを受け取ります。2 号と 3 号を、6 号の先生と呼びます。

2 台のロボットが師弟関係になく、共通の先生もいない場合、その 2 台の知識は互いに独立であると呼びます。1 号の知識は他のすべてのロボットと独立であり（ロボットを製造できるのは 1 号だけだからです）、1 号はどのロボットの先生でもないことに注意してください。

あるロボットの独立数とは、自分より番号が小さく、かつ自分と知識が互いに独立なロボットの個数です。例えば、1 号の独立数は $0$、2 号の独立数は $1$ です（1 号と知識が互いに独立です）。6 号の独立数は $2$ です。1 号と 5 号は 6 号と知識が互いに独立で、2 号と 3 号は先生であり、4 号とは共通の先生である 2 号を持ちます。

新たに製造されるロボットには、3 種類の職業があります。番号 $m$ が、偶数個の異なる奇素数の積に分解できる場合、そのロボットは政治家です。例えば、15 号が該当します。そうでなく、$m$ 自身が奇素数であるか、奇数個の異なる奇素数の積に分解できる場合は軍人です。例えば、3 号や 165 号が該当します。それ以外の番号のロボットは学者で、例えば 2 号、6 号、9 号が該当します。

$m$ 秒目に生まれた $m$ 号は、自分と自分の先生たちのうち、政治家の独立数の総和、軍人の独立数の総和、学者の独立数の総和をそれぞれ知りたいと思っています。しかし、$m$ 号は仕事に忙しく、計算する暇がありません。手伝ってあげてください。

計算しやすいように、Macsy はすでに $m$ を素因数分解してくれました。出力しやすいように、それぞれの総和を $10000$ で割った余りだけを出力してください。

入力

入力ファイル robot.in の 1 行目には、$m$ の異なる素因数の個数を表す正整数 $k$（$1 \leq k \leq 1000$）が与えられます。

続く $k$ 行には、それぞれ 2 つの整数 $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<10{,}000$、$1 \leq e_i \leq 1{,}000{,}000$ です。

出力

出力ファイル robot.out は 3 行からなります。

1 行目には、$m$ 号とその先生たちのうち、すべての政治家の独立数の総和を $10000$ で割った余りを出力してください。

2 行目には、$m$ 号とその先生たちのうち、すべての軍人の独立数の総和を $10000$ で割った余りを出力してください。

3 行目には、$m$ 号とその先生たちのうち、すべての学者の独立数の総和を $10000$ で割った余りを出力してください。

入出力例

入力 1

3
2 1
3 2
5 1

出力 1

8
6
75

注記

$m=2\times3^2\times5=90$ です。90 号には先生が 10 台おり、自分を合わせて全部で 11 台です。政治家は 15 号だけで、軍人は 3 号と 5 号です。学者は 8 台で、番号は $2,6,9,10,18,30,45,90$ です。

小課題

出力ファイルには 3 つの数が含まれます。3 つすべて正しければ、そのテストケースは 10 点です。2 つ正しければ 7 点、1 つ正しければ 4 点、1 つも正しくなければ 0 点です。