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

public class E1189C1 {

    static int BITree[]; 
      
    /* n --> No. of elements present in input array.  
    BITree[0..n] --> Array that represents Binary  
                    Indexed Tree. 
    arr[0..n-1] --> Input array for whic prefix sum  
                    is evaluated. */
  
    // Returns sum of arr[0..index]. This function  
    // assumes that the array is preprocessed and  
    // partial sums of array elements are stored  
    // in BITree[]. 
    public static int getSum(int index) 
    { 
        int sum = 0; // Iniialize result 
      
        // index in BITree[] is 1 more than 
        // the index in arr[] 
        index = index + 1; 
      
        // Traverse ancestors of BITree[index] 
        while(index>0) 
        { 
            // Add current element of BITree  
            // to sum 
            sum += BITree[index]; 
      
            // Move index to parent node in  
            // getSum View 
            index -= index & (-index); 
        } 
        return sum; 
    } 
  
    // Updates a node in Binary Index Tree (BITree) 
    // at given index in BITree. The given value  
    // 'val' is added to BITree[i] and all of  
    // its ancestors in tree. 
    public static void updateBIT(int n, int index,  
                                        int val) 
    { 
        // index in BITree[] is 1 more than  
        // the index in arr[] 
        index = index + 1; 
      
        // Traverse all ancestors and add 'val' 
        while(index <= n) 
        { 
        // Add 'val' to current node of BIT Tree 
        BITree[index] += val; 
      
        // Update index to that of parent  
        // in update View 
        index += index & (-index); 
        } 
    } 
  
    /* Function to construct fenwick tree  
    from given array.*/
    public static void constructBITree(int arr[], int n) 
    { 
        // Initialize BITree[] as 0 
        for(int i=1; i<=n; i++) 
            BITree[i] = 0; 
      
        // Store the actual values in BITree[] 
        // using update() 
        for(int i = 0; i < n; i++) 
            updateBIT(n, i, arr[i]); 
    } 
    
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int [] arr = new int[n];

        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        
        BITree = new int[n + 5]; 
        constructBITree(arr,n);
        
        int q = sc.nextInt();

        for (int i = 0; i < q; i++) {
            int l = sc.nextInt() -1;
            int r = sc.nextInt() -1;
//            if (l == r) 
//                System.out.println(0);
//            else
//                System.out.println(cal(arr,l,r));
            int get_l;
            if (l>0)
                get_l = getSum(l-1);
            else
                get_l = 0;
            int get_r = getSum(r);
            System.out.println((get_r - get_l)/10);
        }
        
    }    
}
