درختی ریشه‌دار در نظر بگیرید که روی راس شماره‌ی $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$ مربوط به درخت ورودی را نشان می‌دهد.

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