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.
import java.util.*;
import java.lang.*;
import java.io.*;
public class Codechef
{   static PrintWriter out=new PrintWriter(System.out);
	static FastScanner in = new FastScanner(System.in);
     static class FastScanner {
        BufferedReader br;
        StringTokenizer stok;
        FastScanner(InputStream is) {
            br = new BufferedReader(new InputStreamReader(is));
        }
        String next() throws IOException {
            while (stok == null || !stok.hasMoreTokens()) {
                String s = br.readLine();
                if (s == null) {
                    return null;
                }
                stok = new StringTokenizer(s);
            }
            return stok.nextToken();
        }
        int ni() throws IOException {
            return Integer.parseInt(next());
        }
        long nl() throws IOException {
            return Long.parseLong(next());
        }
        double nd() throws IOException {
            return Double.parseDouble(next());
        }
        char nc() throws IOException {
            return (char) (br.read());
        }
        String ns() throws IOException {
            return br.readLine();
        }
        int[] nia(int n) throws IOException{
            int a[] = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = ni();
            }
            return a;
        }
        long[] nla(int n) throws IOException {
            long a[] = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nl();
            return a;
        }
        double[] nda(int n)throws IOException {
            double a[] = new double[n];
            for (int i = 0; i < n; i++)
                a[i] = nd();
            return a;
        }
        int [][] imat(int n,int m) throws IOException
        {   int mat[][]=new int[n][m];
            for(int i=0;i<n;i++)
            {   for(int j=0;j<m;j++)
                   mat[i][j]=ni();
            }
            return mat;
        }
    }
    
    ///     PRINTING FUNCTIONS
    
    static void pia(int arr[]) throws IOException
        {   for(int i=0;i<arr.length;i++)
                out.print(arr[i]+" ");
            out.println();
        }
    static void pla(long arr[]) throws IOException
        {   for(int i=0;i<arr.length;i++)
                out.print(arr[i]+" ");
            out.println();
        }
    static void pimat(int mat[][])
        {   for(int i=0;i<mat.length;i++)
            {   for(int j=0;j<mat[0].length;j++)
                    out.print(mat[i][j]);
            out.println();
        }
    }
        
    ///MAIN METHOD
    
    
    
    
	static long mod=Long.MAX_VALUE;
	public static void main (String[] args) throws java.lang.Exception
	{   int i,j;
	    HashMap<Integer,Integer> hm=new HashMap<Integer,Integer>();
		/*  if(hm.containsKey(z))
		        hm.put(z,hm.get(z)+1);
		    else
		        hm.put(z,1);
		 */       
        ArrayList<Integer> arr=new ArrayList<Integer>();
        HashSet<Integer> set=new HashSet<Integer>();
        PriorityQueue<Integer> pq=new PriorityQueue<Integer>();
        /*  int n = in.ni();
            int m = in.ni();
            String s=in.ns();
            int a[]=in.nia(n);
            int b[][]=in.im(n,m);
            pia(a);
		    pimat(b);
        */
        
        
        int n=in.ni();
        long a[]=in.nla(n);
        long temp[]=new long[n+1];
        for(i=1;i<=n;i++)
            temp[i]=temp[i-1]+a[i-1];
       // for(i=0;i<n+1;i++)
        //    out.print(temp[i]+" ");
        //out.println();    
        int q=in.ni();
        while(q--!=0)
        {
            int x=in.ni();
            int y=in.ni();
            long z=temp[y]-temp[x-1];
            //out.println(temp[y]+" "+temp[x-1]);
            out.println(z/10);
        }
        out.close();
	}
	
	
	
	
	
	static long gcd(long a,long b)
	{   if(b==0)
	        return a;
	    return gcd(b,a%b);    
	}
	static long exponent(long a,long n)
	{   long ans=1;
	    while(n!=0)
	    {   if(n%2==0)
	            ans=(ans*a)%mod;
	       a=(a*a)%mod;
	       n=n>>1;
	    }
	    return ans;
	}
	static int binarySearch(int a[], int item, int low, int high) 
    {   if (high <= low) 
            return (item > a[low])?  (low + 1): low; 
        int mid = (low + high)/2; 
        if(item == a[mid]) 
            return mid+1; 
        if(item > a[mid]) 
            return binarySearch(a, item, mid+1, high); 
        return binarySearch(a, item, low, mid-1); 
    } 
}