Localnicii județului Mehedinți definesc haiestra unui număr ca fiind numărul obținut prin înlocuirea acelui număr cu suma cifrelor sale, până ce numărul rămâne cu o singură cifră.

De exemplu haiestra lui $6$ este $6$, haiestra lui $123$ este $1 + 2 + 3 = 6$, iar haiestra lui $8097$ este $6$ deoarece $8 + 0 + 9 + 7 = 24$ și $2 + 4 = 6$.

Pentru a testa dacă ai fost atent, localnicii ți-au oferit numărul $N$ și șirul de $a_1, a_2, \dots a_N$ de numere naturale și te vor pune să răspunzi la $Q$ întrebări. La fiecare întrebare, vei primi două numere $x$ și $y$ ($x \leq y$) și va trebui să răspuzi cu o singură cifră, reprezentând haiestra numărului $a_x \cdot a_{x+1} \cdot ... \cdot a_y$.

Cerință

Răspunde corect la întrebările localnicilor din Mehedinți.

Date de intrare

Pe prima linie a fișierului de intrare cdcq.in se găsește numărul natural $N$. Pe a doua linie se află numerele $a_1, a_2, \cdots a_N$. Pe a treia linie se află numărul natural $Q$. Pe următoarele $Q$ linii se află câte două numere separate printr-un spațiu.

Date de ieșire

În fișierul de ieșire cdcq.out se vor găsi pe $Q$ linii, câte un număr. Pe a $i$-a linie se află răspunsul la a $i$-a întrebare.

Restricții și precizări

• $1 \leq N, Q \leq 300 \ 000$
• $0 \leq a_i \leq 10^9$ pentru fiecare $i$ de la $1$ la $N$.

Exemplu

cdcq.in

5
0 10 26 41 33
3
2 5
3 4
1 2

cdcq.out

6
4
0

Explicație

$10 \cdot 26 \cdot 41 \cdot 33 = 351780$, iar haiestra lui $351780$ este $6$.

$26 \cdot 41 = 1066$, iar haiestra lui $1066$ este $4$.

$0 \cdot 10 = 0$, iar haiestra lui $0$ este $0$.