בשנת 3030, Macsy פורס קבוצת רובוטים על מאדים.

בשנייה הראשונה הוא הביא למאדים את רובוט מספר $1$, שיכול לייצר רובוטים אחרים.

בשנייה השנייה ייצר רובוט $1$ את הרובוט הראשון שלו — רובוט מספר $2$.

בשנייה השלישית ייצר רובוט $1$ רובוט נוסף — רובוט מספר $3$.

בכל שנייה לאחר מכן יכול רובוט $1$ לייצר רובוט חדש. הרובוט שנוצר בשנייה ה־$m$ ממוספר $m$. אפשר לקרוא לו רובוט מספר $m$ או הרובוט ה־$m$.

הרובוטים מתחילים לעבוד מיד לאחר ייצורם. רובוט $m$ נח פעם בכל $m$ שניות. לדוגמה, רובוט $3$ נח בשניות $6,9,12,\ldots$, ועובד בכל יתר הזמן.

כאשר רובוט נח, זיכרונו מושתל במוחו של הרובוט שנוצר באותה שנייה. לדוגמה, כאשר נוצר רובוט $6$, רובוטים $2$ ו־$3$ נחים, ולכן רובוט $6$ מקבל העתקים של זיכרונותיהם. אנו מכנים את רובוטים $2$ ו־$3$ מוריו של רובוט $6$.

אם אין בין שני רובוטים יחס של מורה ותלמיד, ואין להם מורה משותף, נאמר שהידע שלהם בלתי תלוי זה בזה. שימו לב: הידע של רובוט $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$, רוצה לדעת את סכום מספרי העצמאות של כל הפוליטיקאים, של כל החיילים ושל כל המלומדים בקרב עצמו ומוריו. אבל הוא עסוק בעבודה ואין לו זמן לחשב. האם תוכלו לעזור לו?

כדי להקל את החישוב, Macsy כבר פירק עבורכם את $m$ לגורמים ראשוניים. כדי להקל את הפלט, נדרש להדפיס רק את השארית של כל סכום בחלוקה ב־$10000$.

קלט

השורה הראשונה בקובץ הקלט robot.in היא מספר שלם חיובי $k$, כאשר $1 \leq k \leq 1000$. זהו מספר הגורמים הראשוניים השונים של $m$.

כל אחת מ־$k$ השורות הבאות מכילה שני מספרים שלמים $p_i,e_i$, המציינים את הגורם הראשוני ה־$i$ של $m$ ואת המעריך שלו, כאשר $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 מכיל שלוש שורות.

השורה הראשונה היא השארית בחלוקה ב־$10000$ של סכום מספרי העצמאות של כל הפוליטיקאים בקרב רובוט $m$ ומוריו.

השורה השנייה היא השארית בחלוקה ב־$10000$ של סכום מספרי העצמאות של כל החיילים בקרב רובוט $m$ ומוריו.

השורה השלישית היא השארית בחלוקה ב־$10000$ של סכום מספרי העצמאות של כל המלומדים בקרב רובוט $m$ ומוריו.

דוגמאות

קלט 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$.

ניקוד

קובץ הפלט מכיל שלושה מספרים. אם התוכנית מחשבת נכון את שלושתם, מתקבלות 10 נקודות למקרה הבדיקה; אם היא מחשבת נכון שני מספרים, מתקבלות 7 נקודות; אם היא מחשבת נכון מספר אחד, מתקבלות 4 נקודות; ואם אינה מחשבת אף מספר נכון, מתקבלות 0 נקודות.