#include <bits/stdc++.h>
using namespace std;
template <typename T1, typename T2>
void Max(T1& a, T2 b) {
  a = max(a, (T1)b);
}
template <typename T1, typename T2>
void Min(T1& a, T2 b) {
  a = min(a, (T1)b);
}
const int N = 10, M = 100000;
long long a[N][M];
long long r;
struct Node {
  long long id[2][10];
  long long range[2];
  long long num = 0;
  void add(Node o) {
    num += o.num;
    for (int i = 0; i < (r); ++i)
      if (a[i][range[1]] == a[i][o.range[0]] && id[1][i] != o.id[0][i]) {
        num--;
        long long from = id[1][i];
        long long to = o.id[0][i];
        for (int it = 0; it < (2); ++it)
          for (int i = 0; i < (r); ++i)
            if (id[it][i] == from) id[it][i] = to;
        for (int it = 0; it < (2); ++it)
          for (int i = 0; i < (r); ++i)
            if (o.id[it][i] == from) o.id[it][i] = to;
      }
    for (int i = 0; i < (r); ++i) id[1][i] = o.id[1][i];
    range[1] = o.range[1];
  }
};
Node st[2 * M];
void solve() {
  long long c, q;
  cin >> r >> c >> q;
  for (int i = 0; i < (r); ++i)
    for (int j = 0; j < (c); ++j) cin >> a[i][j];
  for (int j = 0; j < (c); ++j) {
    for (int it = 0; it < (2); ++it) st[c + j].range[it] = j;
    for (int i = 0; i < (r); ++i) {
      long long id = (i == 0 || a[i][j] != a[i - 1][j])
                         ? (st[c + j].num++, i * c + j)
                         : st[c + j].id[0][i - 1];
      for (int it = 0; it < (2); ++it) st[c + j].id[it][i] = id;
    }
  }
  for (int i = c - 1; i >= (1); --i) {
    st[i] = st[i * 2];
    st[i].add(st[i * 2 + 1]);
  }
  while (q--) {
    long long lo, hi;
    cin >> lo >> hi;
    vector<long long> left, right;
    for (lo += c - 1, hi += c; lo < hi; lo >>= 1, hi >>= 1) {
      if (lo & 1) left.push_back(lo++);
      if (hi & 1) right.push_back(--hi);
    }
    left.insert(left.end(), right.rbegin(), right.rend());
    Node ans = st[left[0]];
    for (int i = 1; i <= (left.size() - 1); ++i) ans.add(st[left[i]]);
    cout << ans.num << endl;
  }
}
void init() {}
int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  init();
  solve();
  return 0;
}

### Prompt

Your task is to create 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;
template <typename T1, typename T2>
void Max(T1& a, T2 b) {
  a = max(a, (T1)b);
}
template <typename T1, typename T2>
void Min(T1& a, T2 b) {
  a = min(a, (T1)b);
}
const int N = 10, M = 100000;
long long a[N][M];
long long r;
struct Node {
  long long id[2][10];
  long long range[2];
  long long num = 0;
  void add(Node o) {
    num += o.num;
    for (int i = 0; i < (r); ++i)
      if (a[i][range[1]] == a[i][o.range[0]] && id[1][i] != o.id[0][i]) {
        num--;
        long long from = id[1][i];
        long long to = o.id[0][i];
        for (int it = 0; it < (2); ++it)
          for (int i = 0; i < (r); ++i)
            if (id[it][i] == from) id[it][i] = to;
        for (int it = 0; it < (2); ++it)
          for (int i = 0; i < (r); ++i)
            if (o.id[it][i] == from) o.id[it][i] = to;
      }
    for (int i = 0; i < (r); ++i) id[1][i] = o.id[1][i];
    range[1] = o.range[1];
  }
};
Node st[2 * M];
void solve() {
  long long c, q;
  cin >> r >> c >> q;
  for (int i = 0; i < (r); ++i)
    for (int j = 0; j < (c); ++j) cin >> a[i][j];
  for (int j = 0; j < (c); ++j) {
    for (int it = 0; it < (2); ++it) st[c + j].range[it] = j;
    for (int i = 0; i < (r); ++i) {
      long long id = (i == 0 || a[i][j] != a[i - 1][j])
                         ? (st[c + j].num++, i * c + j)
                         : st[c + j].id[0][i - 1];
      for (int it = 0; it < (2); ++it) st[c + j].id[it][i] = id;
    }
  }
  for (int i = c - 1; i >= (1); --i) {
    st[i] = st[i * 2];
    st[i].add(st[i * 2 + 1]);
  }
  while (q--) {
    long long lo, hi;
    cin >> lo >> hi;
    vector<long long> left, right;
    for (lo += c - 1, hi += c; lo < hi; lo >>= 1, hi >>= 1) {
      if (lo & 1) left.push_back(lo++);
      if (hi & 1) right.push_back(--hi);
    }
    left.insert(left.end(), right.rbegin(), right.rend());
    Node ans = st[left[0]];
    for (int i = 1; i <= (left.size() - 1); ++i) ans.add(st[left[i]]);
    cout << ans.num << endl;
  }
}
void init() {}
int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(0);
  init();
  solve();
  return 0;
}

```