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.io.*;
import java.util.*;

public class Solution7 {
    // public static boolean isGood(String str) {
    //     int zeros = 0, ones = 0;
    //     for(int i=0; i<str.length(); i++) {
    //         if(str.charAt(i) == '0')
    //             zeros++;
    //         else
    //              ones++;
    //     }

    //     return (zeros != ones);
    // }

    public static boolean isGood(int res[]) {
        for(int i=0; i<res.length; i++) {
            int prev = i-1 >= 0 ? res[i-1] : res[res.length-1];
            int next = i+1 < res.length ? res[i+1] : res[0];
            if(res[i] >= prev+next) {
                return false;
            }
        }
        return true;
    } 

    public static void print(int arr[]) {
        Arrays.sort(arr);
        System.out.print(arr[arr.length-2]+" ");
        System.out.print(arr[arr.length-1]+" ");
        System.out.print(arr[arr.length-3]+" ");
        for(int i=0; i<arr.length-3; i++)
            System.out.print(arr[i]+" ");
        System.out.println();
    }

    public static boolean fill(int arr[], int res[]) {
        int first  = -1, sec = -1, third = -1;
        for(int i=0; i<arr.length; i++) {
            if(first == -1 || arr[first] < arr[i]) {
                first = i;
            }
        }

        for(int i=0; i<arr.length; i++) {
            if((sec == -1 || arr[sec] < arr[i]) && first != i) {
                sec = i;
            }
        }

        for(int i=0; i<arr.length; i++) {
            if((third == -1 || arr[third] < arr[i]) && first != i && sec != i) {
                third = i;
            }
        }

        res[0] = arr[sec];
        res[1] = arr[first];
        res[2] = arr[third];
        for(int i=0, k = 3; i<arr.length; i++)
            if(i!=first && i!=sec && i!=third)
                {
                    res[k] = arr[i];
                    k++;
                }
        //System.out.println(arr[first]+" "+arr[sec]+" "+arr[third]);
        if(arr[first] < arr[sec]+arr[third]) {
            return true;
        } 
        return false;
    }

    public static int arr[];
    public static int tree[];

    public static void build(int start, int end, int treeIdx) {
        if(start == end) {
            tree[treeIdx] = arr[start];
            return ;
        }
        int mid = (start + end)/2;
        build(start, mid, 2*treeIdx);
        build(mid+1, end, 2*treeIdx+1);
        tree[treeIdx] = tree[2*treeIdx]+tree[2*treeIdx+1];
    }

    public static int query(int start, int end, int treeIdx, int qs, int qe) {
        if(start > qe || end < qs) {
            return 0;
        }

        if(start >=qs && end <= qe) {
            return tree[treeIdx];
        }

        int mid = (start + end)/2;
        return query(start, mid, 2*treeIdx, qs, qe) + query(mid+1, end, 2*treeIdx+1, qs, qe);
        
        //tree[treeIdx] = tree[2*treeIdx]+tree[2*treeIdx+1];
    }

    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine().trim());
        String str[] = br.readLine().trim().split("\\s");
        arr = new int[n];
        tree = new int[n*4];

        for(int i=0; i<n; i++) {
            arr[i] = Integer.parseInt(str[i]);
        }
        int q = Integer.parseInt(br.readLine().trim());
        build(0, n-1, 1);
        while(q > 0) {
            String inp[] = br.readLine().trim().split("\\s");
            int l = Integer.parseInt(inp[0])-1;
            int r = Integer.parseInt(inp[1])-1;
            System.out.println((query(0, n-1, 1, l, r) / 10));
            q--;
        }    
    }
}
