#include <bits/stdc++.h>
using namespace std;
int a[11][100005];
struct node {
  int l[11], r[11];
  int L, R, ans;
};
node st[400005];
int p[41], val[41];
int root(int a) { return p[a] == a ? a : (p[a] = root(p[a])); }
void merge(int a, int b) {
  a = root(a), b = root(b);
  if (a != b) p[a] = b;
}
int n, m, q;
node merge2(node x, node y) {
  if (x.ans == 0)
    return y;
  else if (y.ans == 0)
    return x;
  node ans;
  ans.ans = x.ans + y.ans;
  for (int i = 1; i <= 4 * n; i++) p[i] = i, val[i] = 0;
  for (int i = 1; i <= n; i++) {
    y.l[i] += 2 * n;
    y.r[i] += 2 * n;
  }
  ans.L = x.L;
  ans.R = y.R;
  for (int i = 1; i <= n; i++) {
    if (a[i][x.R] == a[i][y.L]) {
      ans.ans--;
      if (root(x.r[i]) == root(y.l[i])) ans.ans++;
      merge(x.r[i], y.l[i]);
    }
  }
  int cnt = 1;
  for (int i = 1; i <= n; i++) {
    ans.l[i] = x.l[i];
    ans.r[i] = y.r[i];
    if (val[root(ans.l[i])])
      ans.l[i] = val[root(ans.l[i])];
    else {
      val[root(ans.l[i])] = cnt++;
      ans.l[i] = val[root(ans.l[i])];
    }
    if (val[root(ans.r[i])])
      ans.r[i] = val[root(ans.r[i])];
    else {
      val[root(ans.r[i])] = cnt++;
      ans.r[i] = val[root(ans.r[i])];
    }
  }
  return ans;
}
void build(int N, int s, int e) {
  if (s == e) {
    st[N].L = s;
    st[N].R = e;
    int cnt = 1;
    for (int i = 1; i <= n; i++) {
      if (i == 1 || a[i][st[N].L] == a[i - 1][st[N].L]) {
        st[N].l[i] = cnt;
        st[N].r[i] = cnt;
      } else {
        cnt++;
        st[N].l[i] = cnt;
        st[N].r[i] = cnt;
      }
    }
    st[N].ans = cnt;
  } else {
    int mid = (s + e) / 2;
    build(N + N, s, mid);
    build(N + N + 1, mid + 1, e);
    st[N] = merge2(st[N + N], st[N + N + 1]);
  }
}
node query(int N, int s, int e, int l, int r) {
  if (s > r || l > e) {
    node ans;
    ans.ans = 0;
    return ans;
  }
  if (l <= s && e <= r) return st[N];
  int mid = (s + e) / 2;
  return merge2(query(N + N, s, mid, l, r), query(N + N + 1, mid + 1, e, l, r));
}
int main() {
  scanf("%d%d%d", &n, &m, &q);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      scanf("%d", &a[i][j]);
    }
  }
  build(1, 1, m);
  for (int i = 1; i <= q; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    printf("%d\n", query(1, 1, m, l, r).ans);
  }
}

### Prompt

Your challenge is to write a Cpp solution to the following problem:

In his spare time Vladik estimates beauty of the flags.

Every flag could be represented as the matrix n × m which consists of positive integers.

Let's define the beauty of the flag as number of components in its matrix. We call component a set of cells with same numbers and between any pair of cells from that set there exists a path through adjacent cells from same component. Here is the example of the partitioning some flag matrix into components:

<image>

But this time he decided to change something in the process. Now he wants to estimate not the entire flag, but some segment. Segment of flag can be described as a submatrix of the flag matrix with opposite corners at (1, l) and (n, r), where conditions 1 ≤ l ≤ r ≤ m are satisfied.

Help Vladik to calculate the beauty for some segments of the given flag.

Input

First line contains three space-separated integers n, m, q (1 ≤ n ≤ 10, 1 ≤ m, q ≤ 105) — dimensions of flag matrix and number of segments respectively.

Each of next n lines contains m space-separated integers — description of flag matrix. All elements of flag matrix is positive integers not exceeding 106.

Each of next q lines contains two space-separated integers l, r (1 ≤ l ≤ r ≤ m) — borders of segment which beauty Vladik wants to know.

Output

For each segment print the result on the corresponding line.

Example

Input

4 5 4
1 1 1 1 1
1 2 2 3 3
1 1 1 2 5
4 4 5 5 5
1 5
2 5
1 2
4 5


Output

6
7
3
4

Note

Partitioning on components for every segment from first test case:

<image>

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
int a[11][100005];
struct node {
  int l[11], r[11];
  int L, R, ans;
};
node st[400005];
int p[41], val[41];
int root(int a) { return p[a] == a ? a : (p[a] = root(p[a])); }
void merge(int a, int b) {
  a = root(a), b = root(b);
  if (a != b) p[a] = b;
}
int n, m, q;
node merge2(node x, node y) {
  if (x.ans == 0)
    return y;
  else if (y.ans == 0)
    return x;
  node ans;
  ans.ans = x.ans + y.ans;
  for (int i = 1; i <= 4 * n; i++) p[i] = i, val[i] = 0;
  for (int i = 1; i <= n; i++) {
    y.l[i] += 2 * n;
    y.r[i] += 2 * n;
  }
  ans.L = x.L;
  ans.R = y.R;
  for (int i = 1; i <= n; i++) {
    if (a[i][x.R] == a[i][y.L]) {
      ans.ans--;
      if (root(x.r[i]) == root(y.l[i])) ans.ans++;
      merge(x.r[i], y.l[i]);
    }
  }
  int cnt = 1;
  for (int i = 1; i <= n; i++) {
    ans.l[i] = x.l[i];
    ans.r[i] = y.r[i];
    if (val[root(ans.l[i])])
      ans.l[i] = val[root(ans.l[i])];
    else {
      val[root(ans.l[i])] = cnt++;
      ans.l[i] = val[root(ans.l[i])];
    }
    if (val[root(ans.r[i])])
      ans.r[i] = val[root(ans.r[i])];
    else {
      val[root(ans.r[i])] = cnt++;
      ans.r[i] = val[root(ans.r[i])];
    }
  }
  return ans;
}
void build(int N, int s, int e) {
  if (s == e) {
    st[N].L = s;
    st[N].R = e;
    int cnt = 1;
    for (int i = 1; i <= n; i++) {
      if (i == 1 || a[i][st[N].L] == a[i - 1][st[N].L]) {
        st[N].l[i] = cnt;
        st[N].r[i] = cnt;
      } else {
        cnt++;
        st[N].l[i] = cnt;
        st[N].r[i] = cnt;
      }
    }
    st[N].ans = cnt;
  } else {
    int mid = (s + e) / 2;
    build(N + N, s, mid);
    build(N + N + 1, mid + 1, e);
    st[N] = merge2(st[N + N], st[N + N + 1]);
  }
}
node query(int N, int s, int e, int l, int r) {
  if (s > r || l > e) {
    node ans;
    ans.ans = 0;
    return ans;
  }
  if (l <= s && e <= r) return st[N];
  int mid = (s + e) / 2;
  return merge2(query(N + N, s, mid, l, r), query(N + N + 1, mid + 1, e, l, r));
}
int main() {
  scanf("%d%d%d", &n, &m, &q);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      scanf("%d", &a[i][j]);
    }
  }
  build(1, 1, m);
  for (int i = 1; i <= q; i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    printf("%d\n", query(1, 1, m, l, r).ans);
  }
}

```