Bobo מציע פעולת כפל על עצים מושרשים.

יהיו $A$ ו-$B$ שני עצים מושרשים כלשהם. העץ $T=A\cdot B$ נבנה על ידי יצירת עותק של $B$ עבור כל צומת $x\in A$ ואיחוד השורש של עותק זה עם $x$ (ראו את האיור הבא לפרטים נוספים). במקרה זה אנו קוראים ל-$A$ ול-$B$ גורמים של $T$.

ברור שמתקיים $T\cdot1=1\cdot T=T$, כאשר $1$ הוא העץ המושרש בעל צומת אחד בלבד. לכן $1$ הוא גורם של כל עץ מושרש, וכל עץ מושרש הוא גורם של עצמו. אם לעץ מושרש $T$ יש רק את $T$ ואת $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$ מרבי).

שימו לב ש-$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