powersum

Considerăm puterea unui număr natural $a$, notată cu $P(a)$, produsul dintre suma cifrelor lui $a$ și numărul de factori din descompunerea acestuia în factori primi.

Puterea numărului $6$ este $12$, deorece există $2$ factori în desompunerea acestuia în factori primi.

Cerință

Fie $n$ si un șir $V$ cu $n$ elemente. Se dau $Q$ întrebări de forma : pentru o pereche $(l,r)$, calculați $P(V_l) + P(V_{l + 1}) + \dots + P(V_r)$.

Date de intrare

Pe prima linie se află $n$, numărul de elemente, urmat de $n$ elemente. Pe cea de-a treia linie se află $Q$, numărul de întrebări, iar pe următoatele $Q$ linii, câte două valori $l$ și $r$.

Date de ieșire

Se vor afișa $Q$ linii, pe linia $i$ aflându-se răspunsul pentru a $i$ -a. întrebare.

Restricții și precizări

• $1 \leq n,Q \leq 10^6$.
• $2 \leq V_i \leq 10^7$.

Exemplul 1

stdin

6
31 19 38 10 29 9 
6
1 1
3 6
3 3
3 6
1 4
1 5

stdout

4
44
22
44
38
49

Explicație

Pentru prima intrebare rezultatul este $4$ deoarece suma cifrelor lui $31$ este $4$, iar cum acesta este numar prim, va exista doar un singur factor in descompunerea lui in factori primi.