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

public class Stack2 {

    static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader() {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(String file_name) throws IOException {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }
            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException {
            if (din == null)
                return;
            din.close();
        }
    }

    static Reader sc = new Reader();
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        /*
         * For integer input: int n=inputInt();
         * For long input: long n=inputLong();
         * For double input: double n=inputDouble();
         * For String input: String s=inputString();
         * Logic goes here
         * For printing without space: print(a+""); where a is a variable of any datatype
         * For printing with space: printSp(a+""); where a is a variable of any datatype
         * For printing with new line: println(a+""); where a is a variable of any datatype
         */
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] ar = new int[n + 1];
        long[] psum=new long[n+1];
        long sum1=0;
        for (int j = 1; j <= n; j++) {
            ar[j] = sc.nextInt();
            sum1+=ar[j];
            psum[j]=sum1;
        }
        int q = sc.nextInt();

        for (int i = 0; i < q; i++) {
            int l = sc.nextInt();
            int r = sc.nextInt();
            long count = 0;
            long s1=psum[r]-psum[l-1];
            count=s1/10;
          /*  List<Integer> list = new ArrayList<>();
            for(int j=l;j<=r;j++){
                list.add(ar[j]);
            }
            while (list.size() > 1) {
                List<Integer> list1 = new ArrayList<>();
                for (int j = 0; j < list.size(); j += 2) {
                    int sum = list.get(j) + list.get(j + 1);
                    if (sum >= 10) {
                        count++;
                    }
                    list1.add(sum%10);
                }
                list=list1;
            }*/
            System.out.println(count);
        }

        bw.flush();
        bw.close();


    }

    public static void dfs(List<List<Integer>> lists, int i, boolean[] visited) {
        visited[i] = true;
        //System.out.println(lists.get(i)+" "+i);
        for (Integer integer : lists.get(i)) {
            if (!visited[integer]) {
                dfs(lists, integer, visited);
            }
        }
    }


    public static long getAns(int i, int n, long[][] dp1, int[] h1, int[] h2, int choice) {
        if (i < 0) {
            return 0;
        }
        if (choice == 0) {
            if (dp1[i][0] == -1)
                dp1[i][0] = getAns(i - 1, n, dp1, h1, h2, 0);
            if (dp1[i][1] == -1)
                dp1[i][1] = h1[i] + getAns(i - 1, n, dp1, h1, h2, 1);
            if (dp1[i][2] == -1)
                dp1[i][2] = h2[i] + getAns(i - 1, n, dp1, h1, h2, 2);
            return Math.max(dp1[i][0], Math.max(dp1[i][1], dp1[i][2]));
        } else if (choice == 1) {
            if (dp1[i][0] == -1)
                dp1[i][0] = getAns(i - 1, n, dp1, h1, h2, 0);
            if (dp1[i][2] == -1)
                dp1[i][2] = h2[i] + getAns(i - 1, n, dp1, h1, h2, 2);
            return Math.max(dp1[i][0], dp1[i][2]);
        } else {
            if (dp1[i][0] == -1)
                dp1[i][0] = getAns(i - 1, n, dp1, h1, h2, 0);
            if (dp1[i][1] == -1)
                dp1[i][1] = h2[i] + getAns(i - 1, n, dp1, h1, h2, 1);
            return Math.max(dp1[i][0], dp1[i][1]);
        }

    }

    public static void bfs(int r, int c, Queue<int[]> queue, long[][] dis, char[][] map, boolean[][] visited) {
        while (!queue.isEmpty()) {
            int[] ar = queue.poll();
            int x = ar[0];
            int y = ar[1];
            if (x + 1 < r) {
                if (map[x + 1][y] != 'T' && dis[x + 1][y] > (dis[x][y] + 1)) {
                    dis[x + 1][y] = Math.min(dis[x + 1][y], (dis[x][y] + 1));
                    queue.add(new int[]{x + 1, y});
                } /*else if (map[x][y] != map[x + 1][y] && dis[x + 1][y] > (dis[x][y] + 1)) {
                    dis[x + 1][y] = Math.min(dis[x + 1][y], dis[x][y] + 1);
                    queue.add(new int[]{x + 1, y});
                }*/
              /*  if(!visited[x+1][y] ){
                    queue.add(new int[]{x + 1, y});
                    visited[x+1][y]=true;
                }*/


            }
            if (y + 1 < c) {
                if (map[x][y + 1] != 'T' && dis[x][y + 1] > (dis[x][y] + 1)) {
                    dis[x][y + 1] = Math.min(dis[x][y + 1], dis[x][y] + 1);
                    queue.add(new int[]{x, y + 1});
                } /*else if (map[x][y] != map[x][y + 1] && dis[x][y + 1] > (dis[x][y] + 1)) {
                    dis[x][y + 1] = Math.min(dis[x][y + 1], dis[x][y] + 1);
                    queue.add(new int[]{x, y + 1});
                }*/
               /* if( !visited[x][y+1]){
                    queue.add(new int[]{x, y+1});
                    visited[x][y+1]=true;
                }*/


            }
            if (x - 1 >= 0) {
                if (map[x - 1][y] != 'T' && dis[x - 1][y] > (dis[x][y] + 1)) {
                    dis[x - 1][y] = Math.min(dis[x - 1][y], (dis[x][y] + 1));
                    queue.add(new int[]{x - 1, y});
                } /*else if (map[x][y] != map[x - 1][y] && dis[x - 1][y] > (dis[x][y] + 1)) {
                    dis[x - 1][y] = Math.min(dis[x - 1][y], dis[x][y] + 1);
                    queue.add(new int[]{x - 1, y});
                }*/
               /* if(!visited[x-1][y]){
                    queue.add(new int[]{x - 1, y});
                    visited[x-1][y]=true;
                }*/


            }
            if (y - 1 >= 0) {
                if (map[x][y - 1] != 'T' && dis[x][y - 1] > (dis[x][y] + 1)) {
                    dis[x][y - 1] = Math.min(dis[x][y - 1], (dis[x][y] + 1));
                    queue.add(new int[]{x, y - 1});
                } /*else if (map[x][y] != map[x][y - 1] && dis[x][y - 1] > (dis[x][y] + 1)) {
                    dis[x][y - 1] = Math.min(dis[x][y - 1], dis[x][y] + 1);
                    queue.add(new int[]{x, y - 1});
                }*/
               /* if(!visited[x][y-1]){
                    queue.add(new int[]{x , y-1});
                    visited[x][y-1]=true;
                }*/


            }
        }
    }


    public static void dfs1(List<List<Integer>> g, boolean[] visited, Stack<Integer> stack, int num) {
        visited[num] = true;
        for (Integer integer : g.get(num)) {
            if (!visited[integer]) {
                dfs1(g, visited, stack, integer);
            }
        }
        stack.push(num);
    }

    public static void dfs2(List<List<Integer>> g, boolean[] visited, List<Integer> list, int num, int c, int[] raj) {
        visited[num] = true;

        for (Integer integer : g.get(num)) {
            if (!visited[integer]) {
                dfs2(g, visited, list, integer, c, raj);
            }
        }
        raj[num] = c;
        list.add(num);

    }

    public static int inputInt() throws IOException {
        return sc.nextInt();
    }

    public static long inputLong() throws IOException {
        return sc.nextLong();
    }

    public static double inputDouble() throws IOException {
        return sc.nextDouble();
    }

    public static String inputString() throws IOException {
        return sc.readLine();
    }

    public static void print(String a) throws IOException {
        bw.write(a);
    }

    public static void printSp(String a) throws IOException {
        bw.write(a + " ");
    }

    public static void println(String a) throws IOException {
        bw.write(a + "\n");
    }


    public static long getAns(int[] ar, int c, long[][] dp, int i, int sign) {
        if (i < 0) {
            return 1;
        }

        if (c <= 0) {
            return 1;
        }

        dp[i][c] = Math.max(dp[i][c], Math.max(ar[i] * getAns(ar, c - 1, dp, i - 1, sign), getAns(ar, c, dp, i - 1, 1)));
        return dp[i][c];
    }


    public static long power(long a, long b, long c) {
        long ans = 1;
        while (b != 0) {
            if (b % 2 == 1) {
                ans = ans * a;
                ans %= c;
            }
            a = a * a;
            a %= c;
            b /= 2;
        }
        return ans;
    }

    public static long power1(long a, long b, long c) {
        long ans = 1;
        while (b != 0) {
            if (b % 2 == 1) {
                ans = multiply(ans, a, c);
            }
            a = multiply(a, a, c);
            b /= 2;

        }
        return ans;

    }

    public static long multiply(long a, long b, long c) {
        long res = 0;
        a %= c;
        while (b > 0) {
            if (b % 2 == 1) {
                res = (res + a) % c;
            }
            a = (a + a) % c;
            b /= 2;
        }

        return res % c;

    }

    public static long totient(long n) {
        long result = n;
        for (long i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                //sum=sum+2*i;
                while (n % i == 0) {
                    n /= i;
                    // sum=sum+n;
                }
                result -= result / i;

            }
        }
        if (n > 1) {
            result -= result / n;

        }
        return result;
    }


    public static long gcd(long a, long b) {
        if (b == 0) {
            return a;
        } else {
            return gcd(b, a % b);
        }
    }

    public static boolean[] primes(int n) {
        boolean[] p = new boolean[n + 1];
        p[0] = false;
        p[1] = false;
        for (int i = 2; i <= n; i++) {
            p[i] = true;
        }

        for (int i = 2; i * i <= n; i++) {
            if (p[i]) {
                for (int j = i * i; j <= n; j += i) {
                    p[j] = false;
                }
            }

        }
        return p;
    }

    static void bogoSort(int[] a, int c) {
        // if array is not sorted then shuffle the
        // array again
        while (isSorted(a) == false) {
            c++;
            shuffle(a);
        }

    }

    // To generate permuatation of the array
    static void shuffle(int[] a) {
        // Math.random() returns a double positive
        // value, greater than or equal to 0.0 and
        // less than 1.0.
        for (int i = 1; i <= a.length; i++)
            swap(a, i, (int) (Math.random() * i));
    }

    // Swapping 2 elements
    static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    // To check if array is sorted or not
    static boolean isSorted(int[] a) {
        for (int i = 1; i < a.length; i++)
            if (a[i] < a[i - 1])
                return false;
        return true;
    }

}