Bobo เสนอการดำเนินการคูณบนต้นไม้มีราก

ให้ $A$ และ $B$ เป็นต้นไม้มีรากสองต้นใด ๆ จากนั้นสร้าง $T=A\cdot B$ โดยทำสำเนาของ $B$ สำหรับจุดยอดแต่ละจุด $x\in A$ และรวมรากของสำเนานั้นเข้ากับ $x$ (ดูรายละเอียดเพิ่มเติมในรูปต่อไปนี้) เราเรียก $A$ และ $B$ ว่าตัวประกอบของ $T$

เห็นได้ชัดว่า $T\cdot\mathbf{1}=\mathbf{1}\cdot T=T$ โดย $\mathbf{1}$ เป็นต้นไม้มีรากที่มีจุดยอดเพียงจุดเดียว ดังนั้น $\mathbf{1}$ เป็นตัวประกอบของต้นไม้มีรากทุกต้น และต้นไม้มีรากทุกต้นเป็นตัวประกอบของตัวเอง หากต้นไม้มีราก $T$ มีเพียง $T$ และ $\mathbf{1}$ เป็นตัวประกอบ เราเรียก $T$ ว่าต้นไม้เฉพาะ

Bobo มีต้นไม้มีราก $T$ ที่มี $n$ โหนด ซึ่งกำหนดหมายเลขเป็น $1,2,\ldots,n$ เพื่อความสะดวก เขาต้องการแยกตัวประกอบ $T$ ให้เป็นผลคูณของต้นไม้เฉพาะจำนวนมากที่สุดเท่าที่เป็นไปได้ (กล่าวคือ หาสมการ $T=T_1\cdot T_2\cdots T_m$ โดย $T_i$ ($1\le i\le m$) เป็นต้นไม้เฉพาะ และ $m$ มีค่ามากที่สุด)

โปรดทราบว่า $\mathbf{1}$ ไม่ใช่ต้นไม้เฉพาะ

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

ข้อมูลนำเข้ามีกรณีทดสอบตั้งแต่ศูนย์กรณีขึ้นไป และสิ้นสุดเมื่อถึงจุดสิ้นสุดไฟล์ สำหรับแต่ละกรณีทดสอบ:

บรรทัดแรกมีจำนวนเต็ม $n$ ซึ่งเป็นจำนวนโหนด ($2\le n\le10^6$)

บรรทัดที่สองมีจำนวนเต็ม $n-1$ ตัว $p_2,p_3,\ldots,p_n$ โดย $p_i$ เป็นโหนดพ่อของโหนดที่ $i$ ($1\le p_i\le i-1$)

รับประกันว่าผลรวมของ $n$ ทั้งหมดไม่เกิน $10^6$

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

สำหรับแต่ละกรณีทดสอบ ให้พิมพ์จำนวนเต็มแทนจำนวนตัวประกอบเฉพาะมากที่สุด

ตัวอย่าง

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

12
1 1 1 1 2 2 4 5 5 6 10
3
1 1
6
1 1 1 2 3
13
1 1 1 2 2 3 3 4 5 6 7 8

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

3
1
2
1