Bobo mengusulkan operasi perkalian pada pohon berakar.

Misalkan $A$ dan $B$ adalah dua pohon berakar sembarang. Maka $T=A\cdot B$ dibentuk dengan membuat satu salinan $B$ untuk setiap simpul $x\in A$ dan menggabungkan akar salinan ini dengan $x$ (lihat gambar berikut untuk lebih jelasnya). Kita kemudian menyebut $A$ dan $B$ sebagai faktor dari $T$.

Jelas bahwa $T\cdot1=1\cdot T=T$, di mana $1$ adalah pohon berakar yang hanya memiliki satu simpul. Jadi, $1$ adalah faktor dari setiap pohon berakar, dan setiap pohon berakar adalah faktor dari dirinya sendiri. Jika sebuah pohon berakar $T$ hanya memiliki faktor $T$ dan $1$, kita menyebut $T$ sebagai pohon prima.

Bobo memiliki pohon berakar $T$ dengan $n$ simpul yang diberi label $1,2,\ldots,n$. Ia ingin memfaktorkan $T$ menjadi perkalian sebanyak mungkin pohon prima (yaitu, mencari persamaan $T=T_1\cdot T_2\cdots T_m$ di mana $T_i$ ($1\le i\le m$) adalah pohon prima dan $m$ maksimum).

Perhatikan bahwa $1$ bukan pohon prima.

Masukan

Masukan memuat nol atau lebih kasus uji, dan diakhiri oleh akhir berkas. Untuk setiap kasus uji:

Baris pertama memuat bilangan bulat $n$, yaitu banyaknya simpul ($2\le n\le10^6$).

Baris kedua memuat $(n-1)$ bilangan bulat $p_2,p_3,\ldots,p_n$, di mana $p_i$ adalah orang tua simpul ke-$i$ ($1\le p_i\le i-1$).

Dijamin bahwa jumlah semua $n$ tidak melebihi $10^6$.

Keluaran

Untuk setiap kasus uji, cetak sebuah bilangan bulat yang menyatakan banyaknya faktor prima maksimum.

Contoh

Masukan 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

Keluaran 1

3
1
2
1