#include <bits/stdc++.h>
using namespace std;
int n, k, tr[((int)(1e5 + 1)) * 4], chk[((int)(11))][((int)(1e5 + 1))],
    a[((int)(11))][((int)(1e5 + 1))];
pair<int, int> par[((int)(11))][((int)(1e5 + 1))][25];
pair<int, int> findpar(int x, int y, int l) {
  pair<int, int> p = make_pair(x, y);
  if ((l == 0 && chk[x][y] != k) || par[x][y][l] == p) {
    return p;
  }
  return par[x][y][l] = findpar(par[x][y][l].first, par[x][y][l].second, l);
}
void init(int cur, int b, int e, int lv) {
  if (lv >= 25) cout << "bug\n";
  pair<int, int> p, q;
  int i;
  if (b == e) {
    tr[cur] = 1;
    for (i = 2; i <= n; i++) {
      if (a[i][b] != a[i - 1][b])
        tr[cur]++;
      else {
        par[i][b][lv] = make_pair(i - 1, b);
      }
    }
    return;
  }
  int l, r, m, j;
  m = (b + e) >> 1;
  l = (cur << 1);
  r = l + 1;
  init(l, b, m, lv + 1);
  init(r, m + 1, e, lv + 1);
  tr[cur] = tr[l] + tr[r];
  for (i = 1; i <= n; i++) {
    for (j = b; j <= e; j++) par[i][j][lv] = par[i][j][lv + 1];
  }
  for (i = 1; i <= n; i++) {
    if (a[i][m] == a[i][m + 1]) {
      p = findpar(i, m, lv);
      q = findpar(i, m + 1, lv);
      if (p != q) {
        par[p.first][p.second][lv] = q;
        tr[cur]--;
      }
    }
  }
}
int get(int cur, int b, int e, int i, int j, int lv) {
  if (lv >= 25) cout << "bug\n";
  pair<int, int> q, p;
  if (e < i || j < b) return 0;
  if (i <= b && j >= e) {
    for (i = 1; i <= n; i++) {
      par[i][b][0] = findpar(i, b, lv);
      chk[i][b] = k;
      if (e != b) {
        par[i][e][0] = findpar(i, e, lv);
        chk[i][e] = k;
      }
    }
    return tr[cur];
  }
  int l, r, m;
  m = (b + e) >> 1;
  l = (cur << 1);
  r = l + 1;
  l = get(l, b, m, i, j, lv + 1);
  r = get(r, m + 1, e, i, j, lv + 1);
  if (min(l, r) == 0) return l + r;
  for (i = 1; i <= n; i++) {
    if (a[i][m] == a[i][m + 1]) {
      if (chk[i][m] != k) {
        par[i][m][0] = make_pair(i, m);
        chk[i][m] = k;
      }
      if (chk[i][m + 1] != k) {
        par[i][m + 1][0] = make_pair(i, m + 1);
        chk[i][m + 1] = k;
      }
      p = findpar(i, m, 0);
      q = findpar(i, m + 1, 0);
      if (p != q) {
        par[q.first][q.second][0] = p;
        par[p.first][p.second][0] = p;
        chk[q.first][q.second] = k;
        chk[p.first][p.second] = k;
        l--;
      }
    }
  }
  return l + r;
}
int main() {
  int m, q, i, j;
  scanf("%d %d %d", &n, &m, &q);
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= m; j++) {
      scanf("%d", &a[i][j]);
      for (k = 0; k < 25; k++) par[i][j][k] = make_pair(i, j);
    }
  }
  init(1, 1, m, 1);
  for (k = 1; k <= q; k++) {
    scanf("%d %d", &i, &j);
    printf("%d\n", get(1, 1, m, i, j, 1));
  }
  return 0;
}

### Prompt

Generate 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 n, k, tr[((int)(1e5 + 1)) * 4], chk[((int)(11))][((int)(1e5 + 1))],
    a[((int)(11))][((int)(1e5 + 1))];
pair<int, int> par[((int)(11))][((int)(1e5 + 1))][25];
pair<int, int> findpar(int x, int y, int l) {
  pair<int, int> p = make_pair(x, y);
  if ((l == 0 && chk[x][y] != k) || par[x][y][l] == p) {
    return p;
  }
  return par[x][y][l] = findpar(par[x][y][l].first, par[x][y][l].second, l);
}
void init(int cur, int b, int e, int lv) {
  if (lv >= 25) cout << "bug\n";
  pair<int, int> p, q;
  int i;
  if (b == e) {
    tr[cur] = 1;
    for (i = 2; i <= n; i++) {
      if (a[i][b] != a[i - 1][b])
        tr[cur]++;
      else {
        par[i][b][lv] = make_pair(i - 1, b);
      }
    }
    return;
  }
  int l, r, m, j;
  m = (b + e) >> 1;
  l = (cur << 1);
  r = l + 1;
  init(l, b, m, lv + 1);
  init(r, m + 1, e, lv + 1);
  tr[cur] = tr[l] + tr[r];
  for (i = 1; i <= n; i++) {
    for (j = b; j <= e; j++) par[i][j][lv] = par[i][j][lv + 1];
  }
  for (i = 1; i <= n; i++) {
    if (a[i][m] == a[i][m + 1]) {
      p = findpar(i, m, lv);
      q = findpar(i, m + 1, lv);
      if (p != q) {
        par[p.first][p.second][lv] = q;
        tr[cur]--;
      }
    }
  }
}
int get(int cur, int b, int e, int i, int j, int lv) {
  if (lv >= 25) cout << "bug\n";
  pair<int, int> q, p;
  if (e < i || j < b) return 0;
  if (i <= b && j >= e) {
    for (i = 1; i <= n; i++) {
      par[i][b][0] = findpar(i, b, lv);
      chk[i][b] = k;
      if (e != b) {
        par[i][e][0] = findpar(i, e, lv);
        chk[i][e] = k;
      }
    }
    return tr[cur];
  }
  int l, r, m;
  m = (b + e) >> 1;
  l = (cur << 1);
  r = l + 1;
  l = get(l, b, m, i, j, lv + 1);
  r = get(r, m + 1, e, i, j, lv + 1);
  if (min(l, r) == 0) return l + r;
  for (i = 1; i <= n; i++) {
    if (a[i][m] == a[i][m + 1]) {
      if (chk[i][m] != k) {
        par[i][m][0] = make_pair(i, m);
        chk[i][m] = k;
      }
      if (chk[i][m + 1] != k) {
        par[i][m + 1][0] = make_pair(i, m + 1);
        chk[i][m + 1] = k;
      }
      p = findpar(i, m, 0);
      q = findpar(i, m + 1, 0);
      if (p != q) {
        par[q.first][q.second][0] = p;
        par[p.first][p.second][0] = p;
        chk[q.first][q.second] = k;
        chk[p.first][p.second] = k;
        l--;
      }
    }
  }
  return l + r;
}
int main() {
  int m, q, i, j;
  scanf("%d %d %d", &n, &m, &q);
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= m; j++) {
      scanf("%d", &a[i][j]);
      for (k = 0; k < 25; k++) par[i][j][k] = make_pair(i, j);
    }
  }
  init(1, 1, m, 1);
  for (k = 1; k <= q; k++) {
    scanf("%d %d", &i, &j);
    printf("%d\n", get(1, 1, m, i, j, 1));
  }
  return 0;
}

```