+ محدودیت زمان: ۲ ثانیه
+ محدودیت حافظه: ۲۵۶ مگابایت
----------
یک دنباله از اعداد صحیح مثل $a_1, a_2, \dots, a_n\,$ داریم. $q$ درخواست داده می‌شود. دو نوع درخواست داریم. در هر درخواست دو عدد صحیح $l$ و $r$ که $1 \leq l \leq r \leq n$ است داده می‌شود از شما می‌خواهیم همه‌ی اعداد $a_l, a_{l+1}, \dots, a_r\,$ را به $\varphi(a_l), \varphi(a_{l+1}), \dots, \varphi(a_r)\,$ سپس مجموع آن‌ها را بعد از تغییر چاپ کنید.
منظور از $\varphi(k)$ تابع «[فی اویلر](https://fa.wikipedia.org/wiki/%D8%AA%D8%A7%D8%A8%D8%B9_%D9%81%DB%8C_%D8%A7%D9%88%DB%8C%D9%84%D8%B1)» است که تعداد اعداد طبیعی کوچکتر یا مساوی $k$ که نسبت به $k$ اول هستند را نشان می‌دهد.
# ورودی
در سطر اول ورودی، عدد صحیح و مثبت $n$ آمده که تعداد اعضای دنباله‌ی را نشان می‌دهد.
$$1 \leq n \leq 100 \, 000$$
در سطر دوم ورودی، $n$ عدد صحیح که با یک فاصله از هم جدا شده‌اند آمده است. عدد $i$ ام ظاهر شده مقدار $a_i$ را نشان می‌دهد.
$$1 \leq a_i \leq 100 \, 000$$
در سطر سوم ورودی، عدد صحیح $q$ آمده که تعداد درخواست‌ها را نشان می‌دهد.
$$1 \leq q \leq 100 \, 000$$
در $q$ سطر بعدی، در هر سطر یک درخواست می‌آید. هر درخواست به صورت دو عدد $l$ و $r$ نشان داده می‌شود که $l$ و $r$ به ترتیب شروع و پایان بازه‌ی درخواست را نشان می‌دهند.
$$1 \leq l \leq r \leq n$$
# خروجی
به تعداد درخواست‌ها، مقدار مجموع زیربازه را بعد از تغییر گفته شده چاپ کنید.
# مثال
## ورودی نمونه ۱
```
5
12 3 4 18 6
6
1 5
3 4
1 5
1 3
2 5
3 3
```
## خروجی نمونه ۱
```
16
3
6
3
4
1
```