في عام 3030، ينشر Macsy مجموعة من الروبوتات على المريخ.

في الثانية الأولى، نقل الروبوت رقم $1$ إلى المريخ. يستطيع الروبوت رقم $1$ صنع روبوتات أخرى.

في الثانية الثانية، صنع الروبوت رقم $1$ أول روبوت له، وهو الروبوت رقم $2$.

في الثانية الثالثة، صنع الروبوت رقم $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$ هو $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$، وهو عدد العوامل الأولية المختلفة للعدد $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<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$ عشرة معلّمين، ومعه يصبح المجموع أحد عشر روبوتًا. السياسي الوحيد بينهم هو الروبوت $15$؛ والعسكريان هما $3,5$؛ وهناك ثمانية علماء أرقامهم $2,6,9,10,18,30,45,90$.

المهام الفرعية

يحتوي ملف الإخراج على ثلاثة أعداد. إذا حسب برنامجك الأعداد الثلاثة صحيحة، حصلت حالة الاختبار على 10 درجات؛ وإذا حسب عددين صحيحين، حصلت على 7 درجات؛ وإذا حسب عددًا واحدًا صحيحًا، حصلت على 4 درجات؛ وإذا لم يحسب أي عدد صحيحًا، حصلت على 0 درجة.