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.Arrays;
import java.util.Scanner;

// https://codeforces.com/contest/1189/problem/C

//我感觉又是树了，每轮数据总数变为原来的一半，是两个节点配对称为兄弟并生成一个新的父亲节点的过程
//自然要使用 DFS，每次从子节点返回值后将两个子节点的和相加，判断和是否 >= 10 来生成 candy

// 其实并不需要 DFS，只需要使用 DP，循环即可，状态状态转移方程为：
// s[i][j] = s[i-1][j*2] + s[i-1][j*2+1], 然后记得取余
// 因为第 i 行只受第 i-1 行的影响，可删除第一维
// 同时，[j] 被串改不会影响，可以从前往后遍历

// 实测显示，太慢了，原来不需要用 DP
// DP 应该是对各轮的 l, r 来说的
// 

public class Main {
  static int n, q, l, r, max_height, candies;
  static int[] t = new int[100005], sum_memo = new int[100005];
  
  static int sum(int start, int end) {
    return sum_memo[end] - sum_memo[start];
  }
  static void calMemo() {
    for (int i = 1; i < n+1; i++) {
      sum_memo[i] = sum_memo[i-1] + t[i-1];
    }
  }
  
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    
    n = scanner.nextInt();
    for (int i = 0; i < n; i++) {
      t[i] = scanner.nextInt();
    }
    q = scanner.nextInt();
    
    calMemo();
    
    for (int i = 0; i < q; i++) {
      l = scanner.nextInt();
      r = scanner.nextInt();
      
      System.out.println(sum(l-1, r)/10);
//      // Copy 太浪费时间了
//      candies = 0;
//      boolean isFirst = true;
//      // k = 8, 4, 2, 1
//      for (int k = r-l+1; k >= 1; k /=2) {
//        for (int j = 0; j < k/2; j++) {
//          int tmp;
//          if (isFirst) {
//            // 先把数 copy 过来
//            tmp = t[j*2+l-1] + t[j*2+1+l-1];
//          } else {
//            tmp = s[j*2+l-1] + s[j*2+1+l-1];
//          }
//          if (tmp >= 10) {
//            candies++;
//          }
//          s[j+l-1] = tmp % 10;
//        }
//        isFirst = false;
//      }
//      System.out.println(candies);
    }
    scanner.close();
  }
}
