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.
class FTree:

    def __init__(self, f):

        self.n = len(f)

        self.ft = [0] * (self.n + 1)



        for i in range(1, self.n + 1):

            self.ft[i] += f[i - 1]

            if i + self.lsone(i) <= self.n:

                self.ft[i + self.lsone(i)] += self.ft[i]



    def lsone(self, s):

        return s & (-s)



    def query(self, i, j):

        if i > 1:
##########################################################################     edit
            return self.query(1, j) - self.query(1, i - 1)



        s = 0

        while j > 0:

            s += self.ft[j]

            j -= self.lsone(j)



        return s



    def update(self, i, v):

        while i <= self.n:

            self.ft[i] += v

            i += self.lsone(i)



    def select(self, k):

        lo = 1

        hi = self.n



        for _ in range(30):

            mid = (lo + hi) // 2

            if self.query(1, mid) < k:

                lo = mid

            else:

                hi = mid



        return hi



class RUPQ:

    def __init__(self, n):

        self.ftree = FTree([0] * n)



    def query(self, i):

        return self.ftree.query(1, i)



    def update(self, i, j, v):

        self.ftree.update(i, v)

        self.ftree.update(j + 1, -v)



class RURQ:

    def __init__(self, n):

        self.f = FTree([0] * n)

        self.r = RUPQ(n)



    def query(self, i, j):

        if i > 1:

            return self.query(1, j) - self.query(1, i - 1)

        return self.r.query(j) * j - self.f.query(1, j)



    def update(self, i, j, v):

        self.r.update(i, j, v)

        self.f.update(i, v * (i - 1))

        self.f.update(j + 1, -1 * v * j)



#====================================================================================
num = int(input())
data = [int(i) for i in input().split()]

# dic = {}
# w = 1
# for _ in range( 20):
#     dic[w-1] = _
#     w <<= 1

ft = FTree(data)
for _ in range(int(input())):

    a, b = [int(i) for i in input().split()]
    #q = dic[b-a]
    print(ft.query(a, b)//10)

# print("###############")
# for i in range(1,9):
#     print(ft.query(1, i))






# f = [0, 1, 0, 1, 2, 3, 2, 1, 1, 0]

# ft = FTree(f)

# print(ft.query(1, 6) == 7)

# print(ft.query(1, 3) == 1)

# print(ft.select(7) == 6)

# ft.update(5, 1)

# print(ft.query(1, 10) == 12)



# r = RUPQ(10)

# r.update(2, 9, 7)

# r.update(6, 7, 3)

# print(r.query(1) == 0)

# print(r.query(2) == 7)

# print(r.query(3) == 7)

# print(r.query(4) == 7)

# print(r.query(5) == 7)

# print(r.query(6) == 10)

# print(r.query(7) == 10)

# print(r.query(8) == 7)

# print(r.query(9) == 7)

# print(r.query(10) == 0)



# r = RURQ(10)

# r.update(2, 9, 7)

# r.update(6, 7, 3)

# print(r.query(3, 5) == 21)

# print(r.query(7, 8) == 17)



# Example for https://open.kattis.com/problems/fenwick

# from sys import stdin, stdout

#

# def main():

#     n, q = [int(i) for i in stdin.readline().split(' ')]

#     f = FTree([0] * n)

#     for l in stdin.read()[:-1].split('\n'):

#         a = l.split(' ')

#         if a[0] == '?':

#             if a[1] == '0':

#                 stdout.write("0\n")

#             else:

#                 stdout.write("{}\n".format(f.q(1, int(a[1]))))

#         else:

#             f.u(int(a[1]) + 1, int(a[2]))

#

# main()