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.BufferedInputStream;
import java.io.File;
import java.io.FileInputStream;


public class cf_572_2_c {
    public static void main(String[] args) {
        FastScanner f = new FastScanner();
        int n = f.nextInt();
        int a = 0;
        int[] ar = new int[n+1];
        ar[0]=0;
        for (int i = 1; i < n+1; i++) {
            ar[i] = a += f.nextInt();
        }
//        int[] a = f.nextIntArray(n);
        int q = f.nextInt();
        while (q-- > 0) {
            int l = f.nextInt();
            int r = f.nextInt();
            int ans = ar[r] - ar[l-1];

//            for (int i = l; i <=r ; i++) {
//                ans+=a[i];
//            }

            ans/=10;
            System.out.println(ans);



        }
    }


}


class FastScanner {
    public int BS = 1<<16;
    public char NC = (char)0;
    byte[] buf = new byte[BS];
    int bId = 0, size = 0;
    char c = NC;
    double num = 1;
    BufferedInputStream in;

    public FastScanner() {
        in = new BufferedInputStream(System.in, BS);
    }

    public FastScanner(String s) {
        try {
            in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
        }
        catch (Exception e) {
            in = new BufferedInputStream(System.in, BS);
        }
    }

    public char nextChar(){
        while(bId==size) {
            try {
                size = in.read(buf);
            }catch(Exception e) {
                return NC;
            }
            if(size==-1)return NC;
            bId=0;
        }
        return (char)buf[bId++];
    }

    public int nextInt() {
        return (int)nextLong();
    }

    public long nextLong() {
        num=1;
        boolean neg = false;
        if(c==NC)c=nextChar();
        for(;(c<'0' || c>'9'); c = nextChar()) {
            if(c=='-')neg=true;
        }
        long res = 0;
        for(; c>='0' && c <='9'; c=nextChar()) {
            res = (res<<3)+(res<<1)+c-'0';
            num*=10;
        }
        return neg?-res:res;
    }

    public double nextDouble() {
        double cur = nextLong();
        return c!='.' ? cur:cur+nextLong()/num;
    }

    public String next() {
        StringBuilder res = new StringBuilder();
        while(c<=32)c=nextChar();
        while(c>32) {
            res.append(c);
            c=nextChar();
        }
        return res.toString();
    }

    public String nextLine() {
        StringBuilder res = new StringBuilder();
        while(c<=32)c=nextChar();
        while(c!='\n') {
            res.append(c);
            c=nextChar();
        }
        return res.toString();
    }

    public boolean hasNext() {
        if(c>32)return true;
        while(true) {
            c=nextChar();
            if(c==NC)return false;
            else if(c>32)return true;
        }
    }

    public int[] nextIntArray(int n) {
        int[] res = new int[n];
        for(int i = 0; i < n; i++) res[i] = nextInt();
        return res;
    }

    public char[] nextCharArray(int n) {
        char[] res = new char[n];
        for (int i = 0; i < n; i++) {
            res[i] = nextChar();
        }
        return res;
    }

}
