Consider a sequence of digits of length 2^k [a_1, a_2, …, a_{2^k}]. We perform the following operation with it: replace pairs (a_{2i+1}, a_{2i+2}) with (a_{2i+1} + a_{2i+2})mod 10 for 0≤ i<2^{k-1}. For every i where a_{2i+1} + a_{2i+2}≥ 10 we get a candy! As a result, we will get a sequence of length 2^{k-1}.

Less formally, we partition sequence of length 2^k into 2^{k-1} pairs, each consisting of 2 numbers: the first pair consists of the first and second numbers, the second of the third and fourth …, the last pair consists of the (2^k-1)-th and (2^k)-th numbers. For every pair such that sum of numbers in it is at least 10, we get a candy. After that, we replace every pair of numbers with a remainder of the division of their sum by 10 (and don't change the order of the numbers).

Perform this operation with a resulting array until it becomes of length 1. Let f([a_1, a_2, …, a_{2^k}]) denote the number of candies we get in this process. 

For example: if the starting sequence is [8, 7, 3, 1, 7, 0, 9, 4] then:

After the first operation the sequence becomes [(8 + 7)mod 10, (3 + 1)mod 10, (7 + 0)mod 10, (9 + 4)mod 10] = [5, 4, 7, 3], and we get 2 candies as 8 + 7 ≥ 10 and 9 + 4 ≥ 10.

After the second operation the sequence becomes [(5 + 4)mod 10, (7 + 3)mod 10] = [9, 0], and we get one more candy as 7 + 3 ≥ 10. 

After the final operation sequence becomes [(9 + 0) mod 10] = [9]. 

Therefore, f([8, 7, 3, 1, 7, 0, 9, 4]) = 3 as we got 3 candies in total.

You are given a sequence of digits of length n s_1, s_2, … s_n. You have to answer q queries of the form (l_i, r_i), where for i-th query you have to output f([s_{l_i}, s_{l_i+1}, …, s_{r_i}]). It is guaranteed that r_i-l_i+1 is of form 2^k for some nonnegative integer k.

Input

The first line contains a single integer n (1 ≤ n ≤ 10^5) — the length of the sequence.

The second line contains n digits s_1, s_2, …, s_n (0 ≤ s_i ≤ 9).

The third line contains a single integer q (1 ≤ q ≤ 10^5) — the number of queries.

Each of the next q lines contains two integers l_i, r_i (1 ≤ l_i ≤ r_i ≤ n) — i-th query. It is guaranteed that r_i-l_i+1 is a nonnegative integer power of 2.

Output

Output q lines, in i-th line output single integer — f([s_{l_i}, s_{l_i + 1}, …, s_{r_i}]), answer to the i-th query.

Examples

Input


8
8 7 3 1 7 0 9 4
3
1 8
2 5
7 7


Output


3
1
0


Input


6
0 1 2 3 3 5
3
1 2
1 4
3 6


Output


0
0
1

Note

The first example illustrates an example from the statement.

f([7, 3, 1, 7]) = 1: sequence of operations is [7, 3, 1, 7] → [(7 + 3)mod 10, (1 + 7)mod 10] = [0, 8] and one candy as 7 + 3 ≥ 10 → [(0 + 8) mod 10] = [8], so we get only 1 candy.

f([9]) = 0 as we don't perform operations with it.
//package com.company;

//import java.io.BufferedReader;
//import java.io.IOException;
//import java.io.IOException;
//import java.io.InputStreamReader;
//import java.math.BigInteger;
//import java.nio.file.Paths;
import java.util.*;

public class Main {
    public static void main(String[] args) {
        // write your code here
        // BufferedReader s=new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader s=new BufferedReader(new InputStreamReader(System.in));    StringBuilder sb = new StringBuilder();
        Scanner s=new Scanner(System.in);
        //     String[] str=s.readLine().trim().split("\\s+");
        Integer n=s.nextInt();
        Long[] a=new Long[n];Long[] sum=new Long[n];
       for(int i=0;i<n;i++){
           a[i]=s.nextLong();
          if(i>0)sum[i]=sum[i-1]+a[i];else sum[i]=a[i];
       }int m=s.nextInt();
       while(m-->0){
           int x=s.nextInt()-1;int y=s.nextInt()-1;
           if(x>0){
               System.out.println((sum[y]-sum[x-1])/10);
           }else
               System.out.println(sum[y]/10);
       }

    }

    static int gcd(int a, int b)
    {
        if (a == 0)
            return b;
        return gcd(b % a, a);
    }

    // method to return LCM of two numbers
    static int lcm(int a, int b)
    {
        return (a*b)/gcd(a, b);
    }
    static int[] vis;
    static int count;
    static int[] flag;
    static int another;
    static int connected;static int huf=0;
    static void dfs(int i,LinkedList<Integer> [] adj){
        connected++;
        vis[i]=1;if(flag[i]==1) count++;
        if(adj[i]!=null){
            for(int j:adj[i]){
                if(vis[j]==0){
                    if(flag[i]==0) flag[j]=1; else flag[j]=0;

                    dfs(j,adj);
                } else{
                    if(flag[i]==flag[j]){
                        huf=1;
                    }
                }


            }}else{another++;}//return count;
    }






    static  Boolean isCyclicUtil(int v, Boolean visited[], int parent,LinkedList[] adj)
    {
        // Mark the current node as visited
        visited[v] = true;
        Integer i;

        // Recur for all the vertices adjacent to this vertex
        if(adj[v]!=null){
            Iterator<Integer> it = adj[v].iterator();
            while (it.hasNext())
            {
                i = it.next();

                // If an adjacent is not visited, then recur for that
                // adjacent
                if (!visited[i])
                {
                    if (isCyclicUtil(i, visited, v,adj))
                        return true;
                }

                // If an adjacent is visited and not parent of current
                // vertex, then there is a cycle.
                else if (i != parent)
                    return true;
            }}
        return false;
    }

    // Returns true if the graph contains a cycle, else false.
    static Boolean isCyclic(int V,LinkedList<Integer>[] adj)
    {
        // Mark all the vertices as not visited and not part of
        // recursion stack
        Boolean visited[] = new Boolean[V];
        for (int i = 0; i < V; i++)
            visited[i] = false;

        // Call the recursive helper function to detect cycle in
        // different DFS trees
        for (int u = 0; u < V; u++)
            if (!visited[u]) // Don't recur for u if already visited
                if (isCyclicUtil(u, visited, -1,adj))
                    return true;

        return false;
    }

}

class Student
{
    int rollno;
    int color;

    // Constructor
    public Student(int rollno, int color)
    {
        this.rollno = rollno;

        this.color=color;}
    // Used to print student details in main()
    public String toString()
    {
        return this.rollno + " " ;
    }
}

class Sortbyroll implements Comparator<Student>
{
    // Used for sorting in ascending order of
    // roll number
    public int compare(Student a, Student b)
    {
        return a.color - b.color;
    }
}