cdcq

The locals of Mehedinți County define the haiestra of a number as the number obtained by replacing that number with the sum of its digits, until the number is reduced to a single digit.

For example, the haiestra of $6$ is $6$, the haiestra of $123$ is $1 + 2 + 3 = 6$, and the haiestra of $8097$ is $6$ because $8 + 0 + 9 + 7 = 24$ and $2 + 4 = 6$.

To test if you were paying attention, the locals have given you the number $N$ and the sequence of $a_1, a_2, \dots a_N$ of natural numbers and will ask you $Q$ questions. For each question, you will receive two numbers $x$ and $y$ ($x \leq y$) and you will have to answer with a single digit, representing the haiestra of the number $a_x \cdot a_{x+1} \cdot ... \cdot a_y$.

Task

Answer correctly the questions of the locals from Mehedinți.

Input data

The first line of the input file cdcq.in contains the natural number $N$. The second line contains the numbers $a_1, a_2, \cdots a_N$. The third line contains the natural number $Q$. The next $Q$ lines each contain two numbers separated by a space.

Output data

The output file cdcq.out will contain $Q$ lines, each having a number. Each line $i$ contains the answer to question $i$.

Constraints and clarifications

• $1 \leq N, Q \leq 300\ 000$
• $0 \leq a_i \leq 10^9$ for each $i$ from $1$ to $N$.

Example

cdcq.in

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

cdcq.out

6
4
0

Explanation

$10 \cdot 26 \cdot 41 \cdot 33 = 351780$, and the haiestra of $351780$ is $6$.

$26 \cdot 41 = 1066$, and the haiestra of $1066$ is $4$.

$0 \cdot 10 = 0$, and the haiestra of $0$ is $0$.