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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

//import Number_theory.pair;

public class hacker49 {
	public static int r1=0;
	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 nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
	static class pair{
		private long cnt;
		private long[] fq;
		private long[] pref;
		pair(){
			fq=new long[41];
			pref=new long[41];
			cnt=(long)0;
		}	
	}
	
	public static void main(String[] args) {
		OutputStream outputStream =System.out;
	    PrintWriter out =new PrintWriter(outputStream);
		FastReader s=new FastReader();
		int n=s.nextInt();
		int[] a=new int[n+1
		                ];
//		int h=nextPowerOf2(n);
//		System.out.println(h);
//		[] b=new node[2*h-1];
		for(int i=1;i<=n;i++) {
			int g=s.nextInt();
			a[i]=g;
		}
		long[] pre=new long[n+1];
		for(int i=1;i<=n;i++) {
			if(i==1) {
				pre[i]=a[i];
			}else {
				pre[i]=a[i]+pre[i-1];
			}
		}
		int q=s.nextInt();
//		Create(a,b,0,n-1,0);
for(int i=0;i<q;i++) {
	int l=s.nextInt();
	int r=s.nextInt();
	out.println((pre[r]-pre[l-1])/10);
}
		
		
		
		
		
		out.close();
       
	}
	static int nextPowerOf2(int n) 
	{ 
	    n--; 
	    n |= n >> 1; 
	    n |= n >> 2; 
	    n |= n >> 4; 
	    n |= n >> 8; 
	    n |= n >> 16; 
	    n++; 
	      
	    return n; 
	} 

	
	
	public static class node{
		private int a;
		private int b;
		node(int a,int b){
			this.a=a;
			this.b=b;
		}
	}


	public static void Create(node[] arr,node[] segtree,int low,int high,int pos) {
		if(low==high) {
			segtree[pos]=arr[low];
			return;
		}
		int mid=(low+high)/2;
		Create(arr,segtree,low,mid,2*pos+1);
		Create(arr,segtree,mid+1,high,2*pos+2);
		if(segtree[2*pos+1].a+segtree[2*pos+2].a>=10) {
			int a=segtree[2*pos+1].a;
			int b=segtree[2*pos+2].a;
			int c=segtree[2*pos+1].b;
			int d=segtree[2*pos+2].b;
			segtree[pos]=new node((a+b)%10,1+c+d);
		}else {
			int a=segtree[2*pos+1].a;
			int b=segtree[2*pos+2].a;
			int c=segtree[2*pos+1].b;
			int d=segtree[2*pos+2].b;
			segtree[pos]=new node(a+b,c+d);
			
		}
	}
	public static node Query(node[] segtree,int qlow,int qhigh,int low,int high,int pos) {
		if(low>=qlow && high<=qhigh) {
			return segtree[pos];
		}
		if(qhigh<low || qlow>high) {
			return new node(0,0);
		}
		int mid=(low+high)/2;
	 node a=Query(segtree,qlow,qhigh,low,mid,2*pos+1);
	node b=Query(segtree,qlow,qhigh,mid+1,high,2*pos+2);
	int c=a.a;
	int d=b.a;
	if(c+d>=10) {
	node e=new node((c+d)%10,1+a.b+b.b);
	return e;
	}else {
		node e=new node(c+d,a.b+b.b);
		return e;
	}
	}
	
	static class pair1 implements Comparable<pair1>{
		private int a;
		private int b;
		private int c;
		private int d;
		pair1(int a,int b,int c,int d){
			this.a=a;
			this.b=b;
			this.c=c;
			this.d=d;
		}
		public int compareTo(pair1 o) {
			if(this.a<o.a) {
				return 1;
			}else if(this.a==o.a) {
				if(this.b<o.b) {
					return 1;
				}else {
					return -1;
				}
			}else {
				return -1;
			}
				
		}
	}
//	public static class pair5{
//		private int a;
//		private int b;
//		pair5(int a,int b){
//			this.a=a;
//			this.b=b;
//		}
//		public int compareTo(pair5 o) {
//			return Integer.compare(o.b, this.b);
//		}
//	}
//	public static pair5[] merge_sort(pair5[] A, int start, int end) {
//		if (end > start) {
//			int mid = (end + start) / 2;
//			pair5[] v = merge_sort(A, start, mid);
//			pair5[] o = merge_sort(A, mid + 1, end);
//			return (merge(v, o));
//		} else {
//			pair5[] y = new pair5[1];
//			y[0] = A[start];
//			return y;
//		}
//	}
//	public static pair5[] merge(pair5 a[], pair5 b[]) {
////		int count=0;
//		pair5[] temp = new pair5[a.length + b.length];
//		int m = a.length;
//		int n = b.length;
//		int i = 0;
//		int j = 0;
//		int c = 0;
//		while (i < m && j < n) {
//			if (a[i].a < b[j].a) {
//				temp[c++] = a[i++];
//			} else {
//				temp[c++] = b[j++];
//			}
//		}
//		while (i < m) {
//			temp[c++] = a[i++];
//		}
//		while (j < n) {
//			temp[c++] = b[j++];
//		}
//		return temp;
//	}
////	
//	public static int upper_bound(long[] a ,int n,long x) {
//		int l=-1;
//		int r=n;
//		while(r>l+1) {
//			int mid=(l+r)/2;
//			if(a[mid]<x) {
//				l=mid;
//			}else {
//				r=mid;
//			}
//		}
//		return r;
//				
//	}
//
//	
//	
//	public static int lower_bound(pair5[] a ,int n,int x) {
//		int l=-1;
//		int r=n;
//		while(r>l+1) {
//			int mid=(l+r)/2;
//			if(a[mid].a<x) {
//				l=mid;
//			}else {
//				r=mid;
//			}
//		}
//		return l;
//				
//	}
	static boolean isValid(int x,int y,int n,int m) {
		if(x>=1 && x<=n && y>=1 && y<=m) {
			return true;
		}else {
			return false;
		}
	}
	public static boolean equal_Sum_Partition(long[] a,int n) {
		 long sum=0;
		 for(int i=1;i<=n;i++) {
			 sum+=a[i];
		 }
		 if(sum%2!=0) {
			 return false;
		 }else {
			 return subset_Sum_Using_Knapsack(a,n,sum/2);
		 }
	 }
	public static boolean subset_Sum_Using_Knapsack(long[] a,int n,long sum) {
		 int[][] dp=new int[n+1][(int) (sum+1)];
		 for(int i=0;i<=n;i++) {
			 dp[i][0]=1;
		 }
		 for(int i=1;i<=n;i++) {
			 for(int j=1;j<=sum;j++) {
				 if(a[i]<=j) {
					 dp[i][j]=Math.max((dp[i-1][j]),(dp[i-1][(int) (j-a[i])]));
				 }else {
					 dp[i][j]=dp[i-1][j];
				 }
			 }
		 }
		 return dp[n][(int) sum]==1;
	 }
	static long[] fac=new long[1000001];
	static void fac() {
		fac[0]=1;
		for(int i=1;i<=1000000;i++) {
			fac[i]=((fac[i-1]%mod)*(i%mod))%mod;
		}
	}
	static ArrayList<Integer>[] f=new ArrayList[2001];
	public static void init(int n) {
		
		for(int j=1;j<=n;j++) {
		for (int l=1; l<=Math.sqrt(j); l++)
        {
            if (j%l==0)
            {
                // If divisors are equal, print only one
                if (j/l == l) {
                    f[j].add(l);}
      
                else { // Otherwise print both
//                    System.out.print(i+" " + n/i + " " );
            f[j].add(l);
            f[j].add(j/l);
                }
                
            }
        }
		
		}
		
	}
	public static int rod_cutting_with_left_right_strategy(int[] a,int n) {
		int[] dp=new int[n+1];
		dp[1]=a[1];
		for(int i=2;i<=n;i++) {
			dp[i]=a[i];
			int left=1;
			int right=i-1;
			while(left<=right) {
				dp[i]=Math.max(dp[left]+dp[right],dp[i]);
			left++;
			right--;
			}
			
		}
		return dp[n];
	}
	public static long[] merge_sort(long[] A, int start, int end) {
		if (end > start) {
			int mid = (end + start) / 2;
			long[] v = merge_sort(A, start, mid);
			long[] o = merge_sort(A, mid + 1, end);
			return (merge(v, o));
		} else {
			long[] y = new long[1];
			y[0] = A[start];
			return y;
		}
	}
	public static long[] merge(long a[], long b[]) {
//		int count=0;
		long[] temp = new long[a.length + b.length];
		int m = a.length;
		int n = b.length;
		int i = 0;
		int j = 0;
		int c = 0;
		while (i < m && j < n) {
			if (a[i] > b[j]) {
				temp[c++] = a[i++];
			
			} else {
				temp[c++] = b[j++];
			}
		}
		while (i < m) {
			temp[c++] = a[i++];
		}
		while (j < n) {
			temp[c++] = b[j++];
		}
		return temp;
	}
	
	public static long[] merge_sort1(long[] A, int start, int end) {
		if (end > start) {
			int mid = (end + start) / 2;
			long[] v = merge_sort1(A, start, mid);
			long[] o = merge_sort1(A, mid + 1, end);
			return (merge1(v, o));
		} else {
			long[] y = new long[1];
			y[0] = A[start];
			return y;
		}
	}
	public static long[] merge1(long a[], long b[]) {
//		int count=0;
		long[] temp = new long[a.length + b.length];
		int m = a.length;
		int n = b.length;
		int i = 0;
		int j = 0;
		int c = 0;
		while (i < m && j < n) {
			if (a[i] > b[j]) {
				temp[c++] = a[i++];
			
			} else {
				temp[c++] = b[j++];
			}
		}
		while (i < m) {
			temp[c++] = a[i++];
		}
		while (j < n) {
			temp[c++] = b[j++];
		}
		return temp;
	}
	
	static long mod=1000000007;
	static class pair2{
		private long a;
		private int b;
		pair2(long a,int b){
			this.a=a;
			this.b=b;
		}
	}
	




//	for(int i=2;i<=100000;i++) {
		
	
}