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.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.security.acl.LastOwnerException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.Set;
import java.util.SortedSet;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;
import javax.sound.midi.Soundbank;
import org.omg.PortableInterceptor.LOCATION_FORWARD;


public class Main {

  public static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));

  static class FastReader {

    BufferedReader br;
    StringTokenizer st;

    public FastReader() {
      br = new BufferedReader(new
          InputStreamReader(System.in));
    }

    String next() {
      while (st == null || !st.hasMoreElements()) {
        try {
          st = new StringTokenizer(br.readLine());
        } catch (IOException e) {
          e.printStackTrace();
        }
      }
      return st.nextToken();
    }

    int nextInt() {
      return Integer.parseInt(next());
    }

    long nextLong() {
      return Long.parseLong(next());
    }

    double nextDouble() {
      return Double.parseDouble(next());
    }

    String[] nextSArray() {
      String sr[] = null;
      try {
        sr = br.readLine().trim().split(" ");
      } catch (IOException e) {
        e.printStackTrace();
      }
      return sr;
    }

    String nextLine() {
      String str = "";
      try {
        str = br.readLine();
      } catch (IOException e) {
        e.printStackTrace();
      }

      return str;
    }
  }

//  static long mod = 1000000007;
//
//  static ArrayList<String> al=new ArrayList<>();
//  public static int n;
//
//  static  long inversion=0;
//
//  // static long arr[];
//static long tree[] = new long[100000];
//static void MakeTree(long arr[],int s,int e,int i)
//{
//  if(s==e)
//  {
//    tree[i] = arr[s];
//    return;
//  }
//  if(s<e)
//  {
//    int mid = (s+e)/2;
//    MakeTree(arr,s,mid,2*i);
//    MakeTree(arr,mid+1,e,2*i+1);
//    tree[i] = Math.min(tree[2*i],tree[2*i+1]);
//  }
//  return;
//}

//static long MinQuery(int s,int e,int qs,int qe,int i)
//{
//  long t=0;
//
//  if(qe<s || qs>e)
//  { t= Long.MAX_VALUE;}
//  else if(s==e)
//  {
//    t = tree[i];
//  }
//  else if(qs==s&&qe==e)
//  {
//    t = tree[i];
//
//  }
//  else {
//    int mid = (s + e) / 2;
//    t= Math.min(MinQuery(s, mid, qs, qe, 2 * i), MinQuery(mid + 1, e, qs, qe, 2 * i + 1));
//
//  }
//
//  return t;
//}
//
//public static void  UpdateQuery(int s,int e,int i,int qi,long val)
//{
//  if(qi<s||qi>e)
//    return;
//  if(s==e)
//  {
//    if(s==qi)
//      tree[i]=val;
//    return;
//  }
//  int mid = (s+e)/2;
//  UpdateQuery(s,mid,2*i,qi,val);
//  UpdateQuery(mid+1,e,2*i+1,qi,val);
//
//
//
//}

  //public static int QueryTime(int s,int e,int qs,int qe,long k,int i)
//{
//
//  if(qe<s || qs>e)
//  {
//
//    return 0;}
//  if(s>=qs && e<=qe)
//  {
//    int index = Collections.binarySearch(tree[i].al , k);
//    if(index<0)
//      index = Math.abs(index)-1;
//    //System.out.println(tree[i].al.size()-index);
//    return tree[i].al.size()-index;
//  }
//  int mid = (s+e)/2;
//  int m1 = QueryTime(s,mid,qs,qe,k,2*i);
//  int m2 = QueryTime(mid+1,e,qs,qe,k,2*i+1);
//
// // System.out.println((m1+m2) +" "+m1+" "+m2);
//  return m1+m2;
//}
//  public static ArrayList<Long> MakeTree(int s,int e,long arr[],int i)
//  {
//    if(s==e)
//    {
//      ArrayList<Long>al=new ArrayList<>();
//      al.add(arr[s]);
//      Node n = new Node(al);
//      tree[i]=n;
//      return al;
//    }
//    int mid = (s+e)/2;
//    ArrayList<Long> al1=MakeTree(s,mid,arr,2*i);
//    ArrayList<Long> al2=MakeTree(mid+1,e,arr,2*i+1);
//    ArrayList<Long>al=new ArrayList<>();
////    System.out.println("al1" +al1.toString());
////    System.out.println("al2" +al2.toString());
//
//    int ai=0,bi=0;
//    while(ai<al1.size() && bi<al2.size())
//    {
//      if(al1.get(ai)<al2.get(bi))
//      {
//        al.add(al1.get(ai));
//        ++ai;
//      }
//      else
//      {
//        al.add(al2.get(bi));
//        ++bi;
//      }
//    }
//    while(ai<al1.size())
//    {
//      al.add(al1.get(ai++));
//    }
//    while(bi<al2.size())
//    {
//      al.add(al2.get(bi++));
//    }
////    System.out.println("al"+al.toString());
//
//    Node n=new Node(al);
//    tree[i]=n;
//    return al;
//  }
//
//
//  static  int arr[][];
//  static Node tree[]=new Node[400070];
  static long powmodulo(long a, long p) {
    if (p == 0)
      return 1 % mod;
    if (p == 1)
      return a % mod;
    long ans = 1;
    while (p > 0) {
      if ((p & 1) > 0) {
        ans = (ans * a) % mod;
      }
      a = (a * a) % mod;
      p = p >> 1;
    }
    return ans % mod;
  }

  static long mod = 1000000007;

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

  static String s;
  static  int ans=1;

  public static void Find(int [][] arr ,int i,int j,int ci)
  {
    if(ci==48 || (i==6&&j==6))
      return;
    char ch = s.charAt(ci);
      if(ch=='U')
      {
        arr[i-1][j]=1;
        Find(arr,i-1,j,ci+1);
      }
      if(ch=='D')
      {
        arr[i+1][j]=1;
        Find(arr,i+1,j,ci+1);
      }
      if(ch=='L')
      {
        arr[i][j-1]=1;
        Find(arr,i,j-1,ci+1);
      }
      if(ch=='R')
      {
        arr[i][j+1]=1;
        Find(arr,i,j+1,ci+1);
      }
      if(ch=='?')
      {
        int k=0;
        if((i-1)>=0 && arr[i-1][j]==0)
        {
          ++k;
          arr[i-1][j]=1;
          Find(arr, i-1,j,ci+1);
          arr[i-1][j]=0;
        }
        if(i+1<7 && arr[i+1][j]==0)
        {
          ++k;
          arr[i+1][j]=1;
          Find(arr, i+1,j,ci+1);
          arr[i+1][j]=0;
        }
        if(j-1>=0 && arr[i][j-1]==0)
        {
          ++k;
          arr[i][j-1]=1;
          Find(arr, i,j-1,ci+1);
          arr[i][j-1]=0;
        }
        if(j+1<7 && arr[i][j+1]==0)
        {
          ++k;
          arr[i][j+1]=1;
          Find(arr, i,j+1,ci+1);
          arr[i][j+1]=0;
        }
        ans=ans*k;

      }
  }





  public static void main(String[] args) throws Exception {
    FastReader sc = new FastReader();

    int n = sc.nextInt();
    int arr[]=new int[n];
    int sum=0;
    int sumarr[]=new int[n+1];
    sumarr[0]=0;

    for (int i = 0; i <n ; i++) {
      arr[i]=sc.nextInt();
      sumarr[i+1]=sumarr[i]+arr[i];


    }
  // System.out.println(Arrays.toString(sumarr));
    int q=sc.nextInt();
    for (int i = 0; i < q ; i++) {
      int a=sc.nextInt();
      int b=sc.nextInt();
      out.println((sumarr[b]-sumarr[a-1])/10);
    }
    out.close();


  }

}


class Pair
{
  int a; int b;
  Pair(int a,int b)
  {
    this.a=a;
    this.b=b;
  }
}

// out.println(al.toString().replaceAll("[\\[|\\]|,]",""));