#include <bits/stdc++.h>
using namespace std;
struct node {
  int L, R, v;
  int Lf[12], Rf[12];
} Tr[100005 * 4];
int fa[12 * 100005], n, m, h, A[12][100005];
bool bao[12];
int find(int v) {
  if (fa[v] == v) return v;
  return fa[v] = find(fa[v]);
}
void build(int p, int l, int r) {
  Tr[p].L = l;
  Tr[p].R = r;
  if (l == r) {
    for (int i = 1; i <= n; i++) {
      if (A[i][l] != A[i - 1][l]) {
        Tr[p].v++;
        fa[m * (i - 1) + l] = m * (i - 1) + l;
      } else
        fa[m * (i - 1) + l] = m * (i - 2) + l;
      Tr[p].Lf[i] = find(m * (i - 1) + l);
      Tr[p].Rf[i] = find(m * (i - 1) + l);
    }
    return;
  }
  int mid = l + r >> 1;
  build(2 * p, l, mid);
  build(2 * p + 1, mid + 1, r);
  Tr[p].v = Tr[p * 2].v + Tr[p * 2 + 1].v;
  for (int i = 1; i <= n; i++) {
    if (A[i][mid] == A[i][mid + 1]) {
      int a = find((i - 1) * m + mid);
      int b = find((i - 1) * m + mid + 1);
      if (a != b) {
        fa[a] = b;
        Tr[p].v--;
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    Tr[p].Lf[i] = find((i - 1) * m + l);
    Tr[p].Rf[i] = find((i - 1) * m + r);
  }
}
node solve(int p, int l, int r, int a, int b) {
  if (l == a && b == r) {
    return Tr[p];
  }
  int mid = l + r >> 1;
  if (b <= mid)
    return solve(p * 2, l, mid, a, b);
  else if (a > mid)
    return solve(p * 2 + 1, mid + 1, r, a, b);
  else {
    int res = 0;
    node bao1 = solve(p * 2, l, mid, a, mid);
    node bao2 = solve(p * 2 + 1, mid + 1, r, mid + 1, b);
    memset(bao, 0, sizeof(bao));
    for (int i = 1; i <= n; i++) {
      fa[bao1.Rf[i]] = bao1.Rf[i];
      fa[bao2.Lf[i]] = bao2.Lf[i];
      fa[bao1.Lf[i]] = bao1.Lf[i];
      fa[bao2.Rf[i]] = bao2.Rf[i];
    }
    for (int i = 1; i <= n; i++) {
      int a = find(bao1.Rf[i]);
      int b = find(bao2.Lf[i]);
      if (A[i][mid] == A[i][mid + 1]) {
        if (a != b) {
          fa[a] = b;
          res--;
        }
      }
    }
    node tmp;
    tmp.v = res;
    for (int i = 1; i <= n; i++) {
      tmp.Lf[i] = find(bao1.Lf[i]);
      tmp.Rf[i] = find(bao2.Rf[i]);
    }
    tmp.v += bao1.v + bao2.v;
    return tmp;
  }
}
int main() {
  int i, j, k, a, b;
  cin >> n >> m >> h;
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= m; j++) {
      scanf("%d", &A[i][j]);
    }
  }
  build(1, 1, m);
  for (i = 1; i <= h; i++) {
    scanf("%d %d", &a, &b);
    printf("%d\n", solve(1, 1, m, a, b).v);
  }
  return 0;
}

### Prompt

Please create a solution in cpp 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;
struct node {
  int L, R, v;
  int Lf[12], Rf[12];
} Tr[100005 * 4];
int fa[12 * 100005], n, m, h, A[12][100005];
bool bao[12];
int find(int v) {
  if (fa[v] == v) return v;
  return fa[v] = find(fa[v]);
}
void build(int p, int l, int r) {
  Tr[p].L = l;
  Tr[p].R = r;
  if (l == r) {
    for (int i = 1; i <= n; i++) {
      if (A[i][l] != A[i - 1][l]) {
        Tr[p].v++;
        fa[m * (i - 1) + l] = m * (i - 1) + l;
      } else
        fa[m * (i - 1) + l] = m * (i - 2) + l;
      Tr[p].Lf[i] = find(m * (i - 1) + l);
      Tr[p].Rf[i] = find(m * (i - 1) + l);
    }
    return;
  }
  int mid = l + r >> 1;
  build(2 * p, l, mid);
  build(2 * p + 1, mid + 1, r);
  Tr[p].v = Tr[p * 2].v + Tr[p * 2 + 1].v;
  for (int i = 1; i <= n; i++) {
    if (A[i][mid] == A[i][mid + 1]) {
      int a = find((i - 1) * m + mid);
      int b = find((i - 1) * m + mid + 1);
      if (a != b) {
        fa[a] = b;
        Tr[p].v--;
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    Tr[p].Lf[i] = find((i - 1) * m + l);
    Tr[p].Rf[i] = find((i - 1) * m + r);
  }
}
node solve(int p, int l, int r, int a, int b) {
  if (l == a && b == r) {
    return Tr[p];
  }
  int mid = l + r >> 1;
  if (b <= mid)
    return solve(p * 2, l, mid, a, b);
  else if (a > mid)
    return solve(p * 2 + 1, mid + 1, r, a, b);
  else {
    int res = 0;
    node bao1 = solve(p * 2, l, mid, a, mid);
    node bao2 = solve(p * 2 + 1, mid + 1, r, mid + 1, b);
    memset(bao, 0, sizeof(bao));
    for (int i = 1; i <= n; i++) {
      fa[bao1.Rf[i]] = bao1.Rf[i];
      fa[bao2.Lf[i]] = bao2.Lf[i];
      fa[bao1.Lf[i]] = bao1.Lf[i];
      fa[bao2.Rf[i]] = bao2.Rf[i];
    }
    for (int i = 1; i <= n; i++) {
      int a = find(bao1.Rf[i]);
      int b = find(bao2.Lf[i]);
      if (A[i][mid] == A[i][mid + 1]) {
        if (a != b) {
          fa[a] = b;
          res--;
        }
      }
    }
    node tmp;
    tmp.v = res;
    for (int i = 1; i <= n; i++) {
      tmp.Lf[i] = find(bao1.Lf[i]);
      tmp.Rf[i] = find(bao2.Rf[i]);
    }
    tmp.v += bao1.v + bao2.v;
    return tmp;
  }
}
int main() {
  int i, j, k, a, b;
  cin >> n >> m >> h;
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= m; j++) {
      scanf("%d", &A[i][j]);
    }
  }
  build(1, 1, m);
  for (i = 1; i <= h; i++) {
    scanf("%d %d", &a, &b);
    printf("%d\n", solve(1, 1, m, a, b).v);
  }
  return 0;
}

```