#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
int n, m, q;
int tree[4 * N];
int par[4 * N][2][10];
int D[10][N];
void build(int cur, int l, int r) {
  if (l == r) {
    for (int i = 0; i < n; i++) par[cur][0][i] = par[cur][1][i] = l * n + i;
    int cnt = n;
    for (int i = 0; i < n - 1; i++) {
      if (D[i][l] == D[i + 1][l])
        par[cur][0][i + 1] = par[cur][1][i + 1] = par[cur][0][i], cnt--;
    }
    tree[cur] = cnt;
    return;
  } else if (l > r)
    return;
  int M = l + r >> 1;
  build(2 * cur + 1, l, M);
  build(2 * cur + 2, M + 1, r);
  int cnt = tree[2 * cur + 1] + tree[2 * cur + 2], pp[10];
  for (int i = 0; i < n; i++)
    par[cur][0][i] = par[2 * cur + 1][0][i],
    par[cur][1][i] = par[2 * cur + 2][1][i], pp[i] = par[2 * cur + 1][1][i];
  for (int i = 0; i < n; i++) {
    if (D[i][M] == D[i][M + 1]) {
      if (pp[i] != par[2 * cur + 2][0][i]) {
        cnt--;
        int W = pp[i], W1 = par[2 * cur + 2][0][i];
        for (int j = 0; j < n; j++) {
          if (par[cur][0][j] == W) par[cur][0][j] = W1;
          if (par[cur][1][j] == W) par[cur][1][j] = W1;
          if (pp[j] == W) pp[j] = W1;
        }
      }
    }
  }
  tree[cur] = cnt;
}
int qry[4 * N][2][10];
int query(int cur, int l, int r, int x, int y) {
  if (r < x || y < l || l > r) return 0;
  if (x <= l && r <= y) {
    for (int i = 0; i < n; i++)
      qry[cur][0][i] = par[cur][0][i], qry[cur][1][i] = par[cur][1][i];
    return tree[cur];
  }
  int M = l + r >> 1, cnt = 0, c1, c2, pp[10];
  c1 = query(2 * cur + 1, l, M, x, y);
  c2 = query(2 * cur + 2, M + 1, r, x, y);
  for (int i = 0; i < n; i++) {
    if (c1)
      qry[cur][0][i] = qry[2 * cur + 1][0][i], pp[i] = qry[2 * cur + 1][1][i];
    else
      qry[cur][0][i] = qry[2 * cur + 2][0][i];
    if (c2)
      qry[cur][1][i] = qry[2 * cur + 2][1][i];
    else
      qry[cur][1][i] = qry[2 * cur + 1][1][i];
  }
  cnt = c1 + c2;
  if (c1 && c2)
    for (int i = 0; i < n; i++) {
      if (D[i][M] == D[i][M + 1]) {
        if (pp[i] != qry[2 * cur + 2][0][i]) {
          cnt--;
          int W = pp[i], W1 = qry[2 * cur + 2][0][i];
          for (int j = 0; j < n; j++) {
            if (qry[cur][0][j] == W) qry[cur][0][j] = W1;
            if (qry[cur][1][j] == W) qry[cur][1][j] = W1;
            if (pp[j] == W) pp[j] = W1;
          }
        }
      }
    }
  return cnt;
}
int main() {
  int LL, RR;
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m >> q;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) cin >> D[i][j];
  }
  build(0, 0, m - 1);
  for (int i = 0; i < q; i++) {
    cin >> LL >> RR;
    cout << query(0, 0, m - 1, LL - 1, RR - 1) << '\n';
  }
}

### Prompt

Create a solution in cpp for 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;
const int N = 1e5;
int n, m, q;
int tree[4 * N];
int par[4 * N][2][10];
int D[10][N];
void build(int cur, int l, int r) {
  if (l == r) {
    for (int i = 0; i < n; i++) par[cur][0][i] = par[cur][1][i] = l * n + i;
    int cnt = n;
    for (int i = 0; i < n - 1; i++) {
      if (D[i][l] == D[i + 1][l])
        par[cur][0][i + 1] = par[cur][1][i + 1] = par[cur][0][i], cnt--;
    }
    tree[cur] = cnt;
    return;
  } else if (l > r)
    return;
  int M = l + r >> 1;
  build(2 * cur + 1, l, M);
  build(2 * cur + 2, M + 1, r);
  int cnt = tree[2 * cur + 1] + tree[2 * cur + 2], pp[10];
  for (int i = 0; i < n; i++)
    par[cur][0][i] = par[2 * cur + 1][0][i],
    par[cur][1][i] = par[2 * cur + 2][1][i], pp[i] = par[2 * cur + 1][1][i];
  for (int i = 0; i < n; i++) {
    if (D[i][M] == D[i][M + 1]) {
      if (pp[i] != par[2 * cur + 2][0][i]) {
        cnt--;
        int W = pp[i], W1 = par[2 * cur + 2][0][i];
        for (int j = 0; j < n; j++) {
          if (par[cur][0][j] == W) par[cur][0][j] = W1;
          if (par[cur][1][j] == W) par[cur][1][j] = W1;
          if (pp[j] == W) pp[j] = W1;
        }
      }
    }
  }
  tree[cur] = cnt;
}
int qry[4 * N][2][10];
int query(int cur, int l, int r, int x, int y) {
  if (r < x || y < l || l > r) return 0;
  if (x <= l && r <= y) {
    for (int i = 0; i < n; i++)
      qry[cur][0][i] = par[cur][0][i], qry[cur][1][i] = par[cur][1][i];
    return tree[cur];
  }
  int M = l + r >> 1, cnt = 0, c1, c2, pp[10];
  c1 = query(2 * cur + 1, l, M, x, y);
  c2 = query(2 * cur + 2, M + 1, r, x, y);
  for (int i = 0; i < n; i++) {
    if (c1)
      qry[cur][0][i] = qry[2 * cur + 1][0][i], pp[i] = qry[2 * cur + 1][1][i];
    else
      qry[cur][0][i] = qry[2 * cur + 2][0][i];
    if (c2)
      qry[cur][1][i] = qry[2 * cur + 2][1][i];
    else
      qry[cur][1][i] = qry[2 * cur + 1][1][i];
  }
  cnt = c1 + c2;
  if (c1 && c2)
    for (int i = 0; i < n; i++) {
      if (D[i][M] == D[i][M + 1]) {
        if (pp[i] != qry[2 * cur + 2][0][i]) {
          cnt--;
          int W = pp[i], W1 = qry[2 * cur + 2][0][i];
          for (int j = 0; j < n; j++) {
            if (qry[cur][0][j] == W) qry[cur][0][j] = W1;
            if (qry[cur][1][j] == W) qry[cur][1][j] = W1;
            if (pp[j] == W) pp[j] = W1;
          }
        }
      }
    }
  return cnt;
}
int main() {
  int LL, RR;
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m >> q;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) cin >> D[i][j];
  }
  build(0, 0, m - 1);
  for (int i = 0; i < q; i++) {
    cin >> LL >> RR;
    cout << query(0, 0, m - 1, LL - 1, RR - 1) << '\n';
  }
}

```