Năm 3030, Macsy đang triển khai một nhóm rô-bốt trên Sao Hỏa.

Ở giây thứ $1$, anh đưa rô-bốt số $1$ lên Sao Hỏa. Rô-bốt này có thể chế tạo các rô-bốt khác.

Ở giây thứ $2$, rô-bốt số $1$ chế tạo rô-bốt đầu tiên: rô-bốt số $2$.

Ở giây thứ $3$, nó chế tạo một rô-bốt khác: rô-bốt số $3$.

Mỗi giây sau đó, rô-bốt số $1$ đều có thể chế tạo một rô-bốt mới. Rô-bốt được tạo ở giây thứ $m$ có số hiệu $m$. Ta gọi nó là rô-bốt số $m$.

Ngay sau khi được chế tạo, rô-bốt bắt đầu làm việc. Rô-bốt số $m$ nghỉ một lần sau mỗi $m$ giây. Ví dụ, rô-bốt số $3$ nghỉ ở các giây $6,9,12,\ldots$, còn các thời điểm khác đều làm việc.

Khi rô-bốt nghỉ, ký ức của nó được cấy vào bộ não của rô-bốt ra đời lúc đó. Ví dụ, lúc rô-bốt số $6$ ra đời, rô-bốt số $2$ và $3$ đang nghỉ, nên số $6$ nhận được bản sao ký ức của chúng. Ta gọi rô-bốt số $2,3$ là thầy của rô-bốt số $6$.

Nếu hai rô-bốt không có quan hệ thầy trò và không có thầy chung, kiến thức của chúng được gọi là độc lập với nhau. Lưu ý: rô-bốt số $1$ có kiến thức độc lập với tất cả rô-bốt khác (vì chỉ số $1$ biết chế tạo rô-bốt), và không là thầy của bất kỳ rô-bốt nào.

Số độc lập của một rô-bốt là số rô-bốt có số hiệu nhỏ hơn nó và có kiến thức độc lập với nó. Ví dụ, số độc lập của rô-bốt số $1$ là $0$; của số $2$ là $1$ (số $1$ độc lập với nó); của số $6$ là $2$ (số $1,5$ độc lập với nó, số $2,3$ là thầy của nó, còn số $4$ có thầy chung với nó là số $2$).

Các rô-bốt mới có 3 nghề khác nhau. Với rô-bốt số $m$, nếu có thể phân tích $m$ thành tích của một số chẵn các số nguyên tố lẻ khác nhau thì nó là chính khách, ví dụ số $15$. Nếu không, nếu $m$ là số nguyên tố lẻ hoặc có thể phân tích thành tích của một số lẻ các số nguyên tố lẻ khác nhau thì nó là quân nhân, ví dụ số $3$ và $165$. Các rô-bốt còn lại đều là học giả, ví dụ số $2,6,9$.

Rô-bốt số $m$ ra đời ở giây thứ $m$ muốn biết, trong số chính nó và các thầy của nó, tổng số độc lập của tất cả chính khách, của tất cả quân nhân, và của tất cả học giả. Nhưng nó bận làm việc, không có thời gian tính. Bạn có thể giúp không?

Để tiện tính toán, Macsy đã phân tích $m$ thành thừa số nguyên tố. Để tiện xuất kết quả, chỉ cần in phần dư của từng tổng khi chia cho $10000$.

Dữ liệu vào

Dòng đầu tiên của tệp robot.in chứa số nguyên dương $k$ ($1\le k\le1000$), là số thừa số nguyên tố khác nhau của $m$.

Mỗi dòng trong $k$ dòng tiếp theo chứa hai số nguyên $p_i,e_i$, là thừa số nguyên tố thứ $i$ và số mũ của nó ($i=1,2,\ldots,k$). Các số $p_1,p_2,\ldots,p_k$ là các số nguyên tố khác nhau, $m=\prod_{i=1}^{k}p_i^{e_i}$. Các thừa số nguyên tố được cho theo thứ tự tăng dần, tức là $p_1<p_2<\cdots<p_k$. Dữ liệu thỏa mãn $2\le p_i<10000$, $1\le e_i\le1000000$.

Dữ liệu ra

Tệp robot.out gồm ba dòng.

Dòng đầu tiên là phần dư khi chia cho $10000$ của tổng số độc lập của tất cả chính khách trong số rô-bốt $m$ và các thầy của nó.

Dòng thứ hai là phần dư khi chia cho $10000$ của tổng số độc lập của tất cả quân nhân trong số rô-bốt $m$ và các thầy của nó.

Dòng thứ ba là phần dư khi chia cho $10000$ của tổng số độc lập của tất cả học giả trong số rô-bốt $m$ và các thầy của nó.

Ví dụ

Dữ liệu vào 1

3
2 1
3 2
5 1

Dữ liệu ra 1

8
6
75

Ghi chú

$m=2\times3^2\times5=90$. Rô-bốt số $90$ có $10$ thầy, cùng với chính nó là $11$ rô-bốt. Chỉ có chính khách số $15$; quân nhân là số $3,5$; có $8$ học giả, lần lượt là số $2,6,9,10,18,30,45,90$.

Nhiệm vụ con

Tệp kết quả chứa ba số. Nếu chương trình tính đúng cả ba số, bộ kiểm thử được $10$ điểm; đúng hai số được $7$ điểm; đúng một số được $4$ điểm; không đúng số nào được $0$ điểm.