#include <bits/stdc++.h>
using namespace std;
const int L = 1e5 + 5;
struct node {
  int tot, lee[10], ree[10];
};
int IN[L][10], dsu[41], name[41], N, M;
node seg[4 * L], nope;
int fp(int x) {
  if (dsu[x] == x) return x;
  return dsu[x] = fp(dsu[x]);
}
void make(int second, int e, int i) {
  int indi = 1;
  if (second == e) {
    seg[i].lee[0] = seg[i].ree[0] = indi++;
    for (int j = 1; j <= (int)(N - 1); ++j)
      seg[i].lee[j] = seg[i].ree[j] =
          IN[second][j] == IN[second][j - 1] ? seg[i].lee[j - 1] : indi++;
    seg[i].tot = indi - 1;
    return;
  }
  int m = (second + e) >> 1, li = i << 1, ri = i << 1 | 1;
  make(second, m, li), make(m + 1, e, ri);
  for (int j = 1; j <= (int)(4 * N); ++j) dsu[j] = j, name[j] = 0;
  seg[i].tot = seg[li].tot + seg[ri].tot;
  for (int j = 0; j < (int)(N); ++j)
    if (IN[m][j] == IN[m + 1][j] &&
        fp(seg[li].ree[j]) != fp(seg[ri].lee[j] + 2 * N)) {
      --seg[i].tot;
      dsu[fp(seg[li].ree[j])] = fp(seg[ri].lee[j] + 2 * N);
    }
  for (int j = 0; j < (int)(N); ++j) {
    if (name[fp(seg[li].lee[j])])
      seg[i].lee[j] = name[fp(seg[li].lee[j])];
    else
      name[fp(seg[li].lee[j])] = seg[i].lee[j] = indi++;
    if (name[fp(seg[ri].ree[j] + 2 * N)])
      seg[i].ree[j] = name[fp(seg[ri].ree[j] + 2 * N)];
    else
      name[fp(seg[ri].ree[j] + 2 * N)] = seg[i].ree[j] = indi++;
  }
}
node qu(int second, int e, int i, int l, int r) {
  if (l <= second && e <= r) return seg[i];
  if (e < l || second > r) return nope;
  int m = (second + e) >> 1;
  node le = qu(second, m, i << 1, l, r), re = qu(m + 1, e, i << 1 | 1, l, r);
  if (le.tot == -1) return re;
  if (re.tot == -1) return le;
  node ans;
  for (int j = 1; j <= (int)(4 * N); ++j) dsu[j] = j, name[j] = 0;
  ans.tot = le.tot + re.tot;
  for (int j = 0; j < (int)(N); ++j)
    if (IN[m][j] == IN[m + 1][j] && fp(le.ree[j]) != fp(re.lee[j] + 2 * N)) {
      --ans.tot;
      dsu[fp(le.ree[j])] = fp(re.lee[j] + 2 * N);
    }
  int indi = 1;
  for (int j = 0; j < (int)(N); ++j) {
    if (name[fp(le.lee[j])])
      ans.lee[j] = name[fp(le.lee[j])];
    else
      name[fp(le.lee[j])] = ans.lee[j] = indi++;
    if (name[fp(re.ree[j] + 2 * N)])
      ans.ree[j] = name[fp(re.ree[j] + 2 * N)];
    else
      name[fp(re.ree[j] + 2 * N)] = ans.ree[j] = indi++;
  }
  return ans;
}
int main() {
  std::ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  nope.tot = -1;
  int Q, l, r;
  cin >> N >> M >> Q;
  for (int i = 0; i < (int)(N); ++i)
    for (int j = 1; j <= (int)(M); ++j) cin >> IN[j][i];
  make(1, M, 1);
  while (Q--) {
    cin >> l >> r;
    cout << qu(1, M, 1, l, r).tot << endl;
  }
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

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 L = 1e5 + 5;
struct node {
  int tot, lee[10], ree[10];
};
int IN[L][10], dsu[41], name[41], N, M;
node seg[4 * L], nope;
int fp(int x) {
  if (dsu[x] == x) return x;
  return dsu[x] = fp(dsu[x]);
}
void make(int second, int e, int i) {
  int indi = 1;
  if (second == e) {
    seg[i].lee[0] = seg[i].ree[0] = indi++;
    for (int j = 1; j <= (int)(N - 1); ++j)
      seg[i].lee[j] = seg[i].ree[j] =
          IN[second][j] == IN[second][j - 1] ? seg[i].lee[j - 1] : indi++;
    seg[i].tot = indi - 1;
    return;
  }
  int m = (second + e) >> 1, li = i << 1, ri = i << 1 | 1;
  make(second, m, li), make(m + 1, e, ri);
  for (int j = 1; j <= (int)(4 * N); ++j) dsu[j] = j, name[j] = 0;
  seg[i].tot = seg[li].tot + seg[ri].tot;
  for (int j = 0; j < (int)(N); ++j)
    if (IN[m][j] == IN[m + 1][j] &&
        fp(seg[li].ree[j]) != fp(seg[ri].lee[j] + 2 * N)) {
      --seg[i].tot;
      dsu[fp(seg[li].ree[j])] = fp(seg[ri].lee[j] + 2 * N);
    }
  for (int j = 0; j < (int)(N); ++j) {
    if (name[fp(seg[li].lee[j])])
      seg[i].lee[j] = name[fp(seg[li].lee[j])];
    else
      name[fp(seg[li].lee[j])] = seg[i].lee[j] = indi++;
    if (name[fp(seg[ri].ree[j] + 2 * N)])
      seg[i].ree[j] = name[fp(seg[ri].ree[j] + 2 * N)];
    else
      name[fp(seg[ri].ree[j] + 2 * N)] = seg[i].ree[j] = indi++;
  }
}
node qu(int second, int e, int i, int l, int r) {
  if (l <= second && e <= r) return seg[i];
  if (e < l || second > r) return nope;
  int m = (second + e) >> 1;
  node le = qu(second, m, i << 1, l, r), re = qu(m + 1, e, i << 1 | 1, l, r);
  if (le.tot == -1) return re;
  if (re.tot == -1) return le;
  node ans;
  for (int j = 1; j <= (int)(4 * N); ++j) dsu[j] = j, name[j] = 0;
  ans.tot = le.tot + re.tot;
  for (int j = 0; j < (int)(N); ++j)
    if (IN[m][j] == IN[m + 1][j] && fp(le.ree[j]) != fp(re.lee[j] + 2 * N)) {
      --ans.tot;
      dsu[fp(le.ree[j])] = fp(re.lee[j] + 2 * N);
    }
  int indi = 1;
  for (int j = 0; j < (int)(N); ++j) {
    if (name[fp(le.lee[j])])
      ans.lee[j] = name[fp(le.lee[j])];
    else
      name[fp(le.lee[j])] = ans.lee[j] = indi++;
    if (name[fp(re.ree[j] + 2 * N)])
      ans.ree[j] = name[fp(re.ree[j] + 2 * N)];
    else
      name[fp(re.ree[j] + 2 * N)] = ans.ree[j] = indi++;
  }
  return ans;
}
int main() {
  std::ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  nope.tot = -1;
  int Q, l, r;
  cin >> N >> M >> Q;
  for (int i = 0; i < (int)(N); ++i)
    for (int j = 1; j <= (int)(M); ++j) cin >> IN[j][i];
  make(1, M, 1);
  while (Q--) {
    cin >> l >> r;
    cout << qu(1, M, 1, l, r).tot << endl;
  }
  return 0;
}

```