====== GCDTree ======
درختی ریشه‌دار در نظر بگیرید که روی راس شماره‌ی $i$ عدد $a_i$ نوشته شده است. $f_i$ برابر است با تعداد زوج راس‌های نسبت به هم اول در زیردخت راس $i$. به طور دقیق‌تر $f_i$ مساوی است با تعداد زوج‌هایی مانند $(j,k)$ به طوری که $j<k$ باشد، راس‌های $j$ و $k$ در زیردرخت راس $i$ باشند و هم‌چنین اعداد $a_j$ و $a_k$ نسبت به هم اول باشند. دقت کنید که راس $i$ نیز در زیردرخت خودش قرار دارد.

برنامه‌ای بنویسید که درختی را به عنوان ورودی بگیرد و دنباله‌ی $f_i$ ها را برای آن محاسبه کند.
   


===== ورودی =====
در سطر اول ورودی عدد طبیعی $n$، تعداد راس‌های درخت، آمده است.($1\leq n \leq 10^5$)

سطر دوم شامل $n$ عدد طبیعی است که دنباله‌ی $a_1,a_2,…,a_n$ را نشان می‌دهند.($1\leq a_1,a_2,…,a_n\leq 6\times 10^6$)

سطر سوم شامل دنباله‌ی $p_1,p_2,…,p_n$ است که $p_i$ نشان‌گر شماره‌ی پدر راس $i$ است. پدر راس رریشه، صفر در نظر گرفته می‌شود.($0\leq p_1,p_2,…,p_n\leq n$)



===== خروجی =====
در تنها سطر خروجی $n$ عدد چاپ کنید که دنباله‌ی $f_1,f_2,…,f_n$ مربوط به درخت ورودی را نشان می‌دهد.



===== محدودیت‌ها =====


  * محدودیت زمان: ۲ ثانیه
  * محدودیت حافظه: ۲۵۶ مگابایت

===== ورودی و خروجی نمونه =====

<WRAP :en>
^  ورودی نمونه  ^  خروجی نمونه  ^
|5 \\ 4 2 1 3 6 \\ 0 1 1 3 3| 6 0 2 0 0|
|4 \\ 4 3 2 1 \\ 2 3 4 0| 0 1 2 5|
|10 \\ 6 7 10 14 10 5 29 6 17 21 \\ 0 4 10 1 10 4 1 4 7 1| 28 0 0 4 0 0 1 0 0 2|

</WRAP>
  * [[سوال ۴|سوال بعد]]
  * [[سوال ۲|سوال قبل]]