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.*;

public class Candies_CF {
    public  static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter wr = new BufferedWriter(new OutputStreamWriter(System.out));

    static int candies[][];

    public static void main(String args[]) throws IOException {
        int length = Integer.parseInt(br.readLine());

        String values[] = br.readLine().split(" ");

        int vals[] = new int[values.length];

        SegmentTree st = new SegmentTree(0,length-1);

        for (int i = 0; i < vals.length; i++) {
            vals[i] = Integer.parseInt(values[i]);
            st.set(i,vals[i]);
        }

        /*candies = new int[values.length][values.length];

        for (int i = 0; i < candies.length; i++) {
            for (int j = 0; j < candies.length; j++) {
                candies[i][j] = -1;
            }
        }*/

        //Solve(0,values.length-1,vals);

        int queries = Integer.parseInt(br.readLine());

        for (int i = 0; i < queries; i++) {
            String couple[] = br.readLine().split(" ");
            int begin = Integer.parseInt(couple[0]);
            int finish = Integer.parseInt(couple[1]);

            wr.write(st.getVal(begin-1,finish-1)[1]+"\n");
        }

        wr.flush();
    }

    private static int[] Solve(int izq,int der, int[] vals){
        if(der == izq){
            candies[izq][der] = 0;
            return new int[]{vals[der], 0};
        }else{
            int mid = (der+izq)/2;
            int lefVal[] = Solve(izq, mid, vals);
            int rigVal[] = Solve(mid+1,der,vals);

            int candi =  rigVal[1] + lefVal[1];
            int value = rigVal[0] + lefVal[0];

            if(value >= 10){
                value %= 10;
                candi++;
            }

            candies[izq][der] = candi;
            return new int[]{value,candi};
        }
    }
}

class SegmentTree {
    int start, end;
    SegmentTree leftTree, rightTree;
    int [] Value;

    public SegmentTree(int start, int end) {
        this.start = start;
        this.end = end;
        this.Value = new int[2];
        if(start == end) {  // es una hoja
            leftTree = rightTree = null;
            return;
        }
        int mid = (start + end) / 2;
        leftTree = new SegmentTree(start, mid);
        rightTree = new SegmentTree(mid + 1, end);
    }

    public void set(int pos, int value) {
        if(start == end) {
            Value = new int[]{value,0};
            return;
        }

        int mid = (start + end) / 2;

        if(pos <= mid)
            leftTree.set(pos, value);
        else
            rightTree.set(pos, value);

        int candi =  leftTree.Value[1] + rightTree.Value[1];
        int v = leftTree.Value[0] + rightTree.Value[0];

        if(v >= 10){
            v %= 10;
            candi++;
        }

        Value = new int[]{v,candi};
    }


    public int[] getVal(int low, int high) {
        if(start == low && end == high)
            return Value;

        int mid = (start + end) / 2;

        // [low,high] totalmente incluido en [start,mid]
        if(high <= mid)
            return leftTree.getVal(low, high);

        // [low,high] totalmente incluido en [mid+1,end]
        if(low > mid)
            return rightTree.getVal(low, high);

        // debemos dividir el intervalo en [low,mid] y [mid+1,high]
        int left[] = leftTree.getVal(low, mid);
        int right[] = rightTree.getVal(mid+1, high);

        int candi =  left[1] + right[1];
        int v = left[0] + right[0];

        if(v >= 10){
            v %= 10;
            candi++;
        }

        return new int[]{v,candi};

    }

}

