#include <bits/stdc++.h>
using namespace std;
bool isPrime(long long n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  for (long long i = 5; i * i <= n; i = i + 6) {
    if (n % i == 0 || n % (i + 2) == 0) return false;
  }
  return true;
}
long long gcd(long long a, long long b) {
  if (a == 0) return b;
  if (a < b) swap(a, b);
  return gcd(a % b, b);
}
long long gcdextended(long long a, long long b, long long &x, long long &y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  long long x1, y1, gcd = gcdextended(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return gcd;
}
long long modinverse(long long a, long long m) {
  long long x, y;
  long long g = gcdextended(a, m, x, y);
  if (g != 1) {
    cout << "NOT POSSIBLE";
    return -1;
  } else
    return (x % m + m) % m;
}
long long po(long long x, long long y) {
  long long res = 1;
  while (y > 0) {
    if (y & 1) res = (res * x);
    y = y >> 1;
    x = (x * x);
  }
  return res;
}
long long pomod(long long x, long long y, long long p) {
  long long res = 1;
  x = x % p;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
void bfs(long long second, vector<vector<long long> > &v,
         vector<long long> &vis, vector<long long> &le) {
  vis[second] = 1;
  long long p, i;
  le[second] = 0;
  queue<long long> q;
  q.push(second);
  while (!q.empty()) {
    p = q.front();
    q.pop();
    for (i = 0; i < v[p].size(); i++) {
      if (!vis[v[p][i]]) {
        vis[v[p][i]] = 1;
        q.push(v[p][i]);
        le[v[p][i]] = le[p] + 1;
      }
    }
  }
}
long long root(long long x, vector<long long> &id) {
  while (id[x] != x) {
    id[x] = id[id[x]];
    x = id[x];
  }
  return x;
}
void uni(long long x, long long y, vector<long long> &id) {
  long long a = root(x, id);
  long long b = root(y, id);
  id[a] = id[b];
}
long long mst(vector<pair<long long, pair<long long, long long> > > &e,
              vector<long long> &id) {
  long long x, y, i, j;
  long long mic = 0, c;
  for (i = 0; i < e.size(); i++) {
    x = e[i].second.first;
    y = e[i].second.second;
    c = e[i].first;
    if (root(x, id) != root(y, id)) {
      uni(x, y, id);
      mic += c;
    }
  }
  return mic;
}
void dfs(long long second, vector<vector<long long> > &v,
         vector<long long> &vis) {
  vis[second] = 1;
  long long i;
  for (i = 0; i < v[second].size(); i++) {
    if (!vis[v[second][i]]) dfs(v[second][i], v, vis);
  }
}
bool sec(const pair<long long, long long> &a,
         const pair<long long, long long> &b) {
  return a.second > b.second;
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  srand(time(NULL));
  ;
  long long n, i;
  cin >> n;
  long long a[n], p[n], x, y, q;
  for (i = 0; i < n; i++) {
    cin >> a[i];
    p[i] = a[i];
    if (i > 0) p[i] += p[i - 1];
  }
  cin >> q;
  for (i = 0; i < q; i++) {
    cin >> x >> y;
    --x, --y;
    if (x == 0)
      cout << p[y] / 10 << endl;
    else
      cout << (p[y] - p[x - 1]) / 10 << endl;
  }
}

### Prompt

Develop a solution in cpp to the problem described below:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
bool isPrime(long long n) {
  if (n <= 1) return false;
  if (n <= 3) return true;
  if (n % 2 == 0 || n % 3 == 0) return false;
  for (long long i = 5; i * i <= n; i = i + 6) {
    if (n % i == 0 || n % (i + 2) == 0) return false;
  }
  return true;
}
long long gcd(long long a, long long b) {
  if (a == 0) return b;
  if (a < b) swap(a, b);
  return gcd(a % b, b);
}
long long gcdextended(long long a, long long b, long long &x, long long &y) {
  if (a == 0) {
    x = 0;
    y = 1;
    return b;
  }
  long long x1, y1, gcd = gcdextended(b % a, a, x1, y1);
  x = y1 - (b / a) * x1;
  y = x1;
  return gcd;
}
long long modinverse(long long a, long long m) {
  long long x, y;
  long long g = gcdextended(a, m, x, y);
  if (g != 1) {
    cout << "NOT POSSIBLE";
    return -1;
  } else
    return (x % m + m) % m;
}
long long po(long long x, long long y) {
  long long res = 1;
  while (y > 0) {
    if (y & 1) res = (res * x);
    y = y >> 1;
    x = (x * x);
  }
  return res;
}
long long pomod(long long x, long long y, long long p) {
  long long res = 1;
  x = x % p;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
void bfs(long long second, vector<vector<long long> > &v,
         vector<long long> &vis, vector<long long> &le) {
  vis[second] = 1;
  long long p, i;
  le[second] = 0;
  queue<long long> q;
  q.push(second);
  while (!q.empty()) {
    p = q.front();
    q.pop();
    for (i = 0; i < v[p].size(); i++) {
      if (!vis[v[p][i]]) {
        vis[v[p][i]] = 1;
        q.push(v[p][i]);
        le[v[p][i]] = le[p] + 1;
      }
    }
  }
}
long long root(long long x, vector<long long> &id) {
  while (id[x] != x) {
    id[x] = id[id[x]];
    x = id[x];
  }
  return x;
}
void uni(long long x, long long y, vector<long long> &id) {
  long long a = root(x, id);
  long long b = root(y, id);
  id[a] = id[b];
}
long long mst(vector<pair<long long, pair<long long, long long> > > &e,
              vector<long long> &id) {
  long long x, y, i, j;
  long long mic = 0, c;
  for (i = 0; i < e.size(); i++) {
    x = e[i].second.first;
    y = e[i].second.second;
    c = e[i].first;
    if (root(x, id) != root(y, id)) {
      uni(x, y, id);
      mic += c;
    }
  }
  return mic;
}
void dfs(long long second, vector<vector<long long> > &v,
         vector<long long> &vis) {
  vis[second] = 1;
  long long i;
  for (i = 0; i < v[second].size(); i++) {
    if (!vis[v[second][i]]) dfs(v[second][i], v, vis);
  }
}
bool sec(const pair<long long, long long> &a,
         const pair<long long, long long> &b) {
  return a.second > b.second;
}
int main() {
  ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  srand(time(NULL));
  ;
  long long n, i;
  cin >> n;
  long long a[n], p[n], x, y, q;
  for (i = 0; i < n; i++) {
    cin >> a[i];
    p[i] = a[i];
    if (i > 0) p[i] += p[i - 1];
  }
  cin >> q;
  for (i = 0; i < q; i++) {
    cin >> x >> y;
    --x, --y;
    if (x == 0)
      cout << p[y] / 10 << endl;
    else
      cout << (p[y] - p[x - 1]) / 10 << endl;
  }
}

```