ในปี 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$ เองเป็นจำนวนเฉพาะคี่ หรือเขียน $m$ เป็นผลคูณของจำนวนเฉพาะคี่ที่แตกต่างกันจำนวนคี่ตัวได้ มันจะเป็นทหาร เช่น หมายเลข $3$ และ $165$ หุ่นยนต์หมายเลขอื่น ๆ เป็นนักวิชาการ เช่น หมายเลข $2,6,9$

หุ่นยนต์หมายเลข $m$ ที่เกิดในวินาทีที่ $m$ ต้องการทราบผลรวมจำนวนอิสระของนักการเมืองทั้งหมด ผลรวมจำนวนอิสระของทหารทั้งหมด และผลรวมจำนวนอิสระของนักวิชาการทั้งหมด ในบรรดาตัวมันเองและครูของมัน แต่หุ่นยนต์หมายเลข $m$ มัวทำงานจนไม่มีเวลาคำนวณ คุณช่วยมันได้หรือไม่

เพื่อให้คุณคำนวณได้สะดวก Macsy ได้แยกตัวประกอบเฉพาะของ $m$ ให้แล้ว เพื่อความสะดวกในการแสดงผล ต้องการเพียงเศษของผลรวมเมื่อหารด้วย $10000$

ข้อมูลนำเข้า

บรรทัดแรกของไฟล์ข้อมูลนำเข้า robot.in เป็นจำนวนเต็มบวก $k$ ($1 \le k \le 1000$) โดย $k$ คือจำนวนตัวประกอบเฉพาะที่แตกต่างกันของ $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 \le p_i<10000$, $1 \le e_i \le 1000000$

ข้อมูลส่งออก

ไฟล์ข้อมูลส่งออก robot.out มีสามบรรทัด

บรรทัดแรกเป็นเศษเมื่อหารด้วย $10000$ ของผลรวมจำนวนอิสระของนักการเมืองทั้งหมด ในบรรดาหุ่นยนต์หมายเลข $m$ และครูของมัน

บรรทัดที่สองเป็นเศษเมื่อหารด้วย $10000$ ของผลรวมจำนวนอิสระของทหารทั้งหมด ในบรรดาหุ่นยนต์หมายเลข $m$ และครูของมัน

บรรทัดที่สามเป็นเศษเมื่อหารด้วย $10000$ ของผลรวมจำนวนอิสระของนักวิชาการทั้งหมด ในบรรดาหุ่นยนต์หมายเลข $m$ และครูของมัน

ตัวอย่าง

ข้อมูลนำเข้า 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 คะแนน