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.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        FastReader fr = new FastReader();
        FastWriter fw = new FastWriter();
        int n = fr.nextInt();
        int arr[] = new int[n];
        for (int i = 0; i < n; i++) arr[i] = fr.nextInt();
        SegmentTree segmentTree = new SegmentTree(arr);
        int q = fr.nextInt();
        while (q-- > 0) {
            int l = fr.nextInt();
            int r = fr.nextInt();
            fw.println(segmentTree.query(1, 0, arr.length - 1, l - 1, r - 1).candies);
        }
    }

}

class SegmentTree {
    int sum[];
    int candies[];
    int arr[];

    SegmentTree(int arr[]) {
        sum = new int[arr.length * 4];
        candies = new int[arr.length * 4];
        this.arr = arr;
        build(1, 0, arr.length - 1);
    }

    private void build(int i, int l, int h) {
        int mid = l + (h - l) / 2;
        if (l == h) {
            sum[i] = arr[l];
            candies[i] = 0;
        } else {
            build(2 * i, l, mid);
            build(2 * i + 1, mid + 1, h);
            sum[i] = sum[2 * i] + sum[2 * i + 1];
            candies[i] = candies[2 * i] + candies[2 * i + 1];
            if (sum[i] >= 10) {
                sum[i] %= 10;
                candies[i]++;
            }
        }
    }

    public Pair query(int i, int l, int h, int ql, int qh) {
        if (l == ql && h == qh) {
            return new Pair(sum[i], candies[i]);
        }
        int mid = l + (h - l) / 2;
        if (ql > mid) {
            return query(2 * i + 1, mid + 1, h, ql, qh);
        }
        if (qh <= mid) {
            return query(2 * i, l, mid, ql, qh);
        }
        Pair lpair = query(2 * i, l, mid, ql, mid);
        Pair rpair = query(2 * i + 1, mid + 1, h, mid + 1, qh);
        int sum = lpair.sum + rpair.sum;
        int candies = lpair.candies + rpair.candies;
        if (sum >= 10) {
            sum -= 10;
            candies++;
        }
        return new Pair(sum, candies);
    }
}

class Pair {
    public Pair(int sum, int candies) {
        this.sum = sum;
        this.candies = candies;
    }

    int sum, candies;
}

class FastReader {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st;

    String nextString() throws IOException {
        if (st == null || !st.hasMoreTokens()) {
            st = new StringTokenizer(br.readLine());
        }
        return st.nextToken();
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextString());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextString());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextString());
    }
}

class FastWriter {
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    void print(Object o) throws IOException {
        bw.write(o.toString());
        bw.flush();
    }

    void println(Object o) throws IOException {
        print(o.toString() + "\n");
    }

    void printSp(Object o) throws IOException {
        print(o.toString() + " ");
    }
}