#include <bits/stdc++.h>
using namespace std;
template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  os << '{';
  for (int i = (0), __i = (((int)(vec).size())); i < __i; i++) {
    os << vec[i];
    if (i + 1 != ((int)(vec).size())) os << ',';
  }
  os << '}';
  return os;
}
template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &par) {
  os << '(' << par.first << ',' << par.second << ')';
  return os;
}
int gcd(int x, int y) { return y ? gcd(y, x % y) : abs(x); }
template <class T>
T sqr(T x) {
  return x * x;
}
int n, m, q;
int flag[10][100000];
struct Vert {
  int left[10];
  int right[10];
  int comps;
};
Vert tree[400000];
bool used[10][100000];
int mask[1000000];
int numb = 0;
Vert combine(Vert v1, Vert v2) {
  Vert v;
  bool f = false;
  int stitch = 0;
  for (int i = (0), __i = (n); i < __i; i++) {
    if (mask[v1.right[i]] == mask[v2.left[i]] && v1.right[i] != v2.left[i]) {
      int nn = v2.left[i];
      for (int j = (0), __j = (n); j < __j; j++) {
        if (v1.left[j] == nn) v1.left[j] = v1.right[i];
        if (v1.right[j] == nn) v1.right[j] = v1.right[i];
        if (v2.left[j] == nn) v2.left[j] = v1.right[i];
        if (v2.right[j] == nn) v2.right[j] = v1.right[i];
      }
      stitch++;
    }
  }
  for (int i = (0), __i = (n); i < __i; i++) {
    v.left[i] = v1.left[i];
    v.right[i] = v2.right[i];
  }
  v.comps = v1.comps + v2.comps - stitch;
  return v;
}
void build(int v, int l, int r) {
  if (l == r) {
    int cur;
    for (int i = (0), __i = (n); i < __i; i++) {
      if (i == 0 || flag[i - 1][l] != flag[i][l]) {
        cur = numb++;
        mask[cur] = flag[i][l];
        tree[v].comps++;
      }
      tree[v].left[i] = tree[v].right[i] = cur;
    }
    return;
  }
  int mid = (l + r) / 2;
  build(2 * v + 1, l, mid);
  build(2 * v + 2, mid + 1, r);
  tree[v] = combine(tree[2 * v + 1], tree[2 * v + 2]);
}
Vert get_res(int v, int tl, int tr, int l, int r) {
  if (tl == l && tr == r) return tree[v];
  int mid = (tl + tr) / 2;
  if (l > mid) return get_res(2 * v + 2, mid + 1, tr, l, r);
  if (r <= mid) return get_res(2 * v + 1, tl, mid, l, r);
  Vert v1 = get_res(2 * v + 1, tl, mid, l, mid);
  Vert v2 = get_res(2 * v + 2, mid + 1, tr, mid + 1, r);
  return combine(v1, v2);
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m >> q;
  for (int i = (0), __i = (n); i < __i; i++)
    for (int j = (0), __j = (m); j < __j; j++) cin >> flag[i][j];
  int num = 1000001;
  for (int i = (0), __i = (n); i < __i; i++)
    for (int j = (0), __j = (m); j < __j; j++) {
      if (used[i][j]) continue;
      int cur = flag[i][j];
      queue<pair<int, int> > que;
      que.push({i, j});
      used[i][j] = true;
      while (!que.empty()) {
        pair<int, int> u = que.front();
        que.pop();
        flag[u.first][u.second] = num;
        if (u.first > 0 && flag[u.first - 1][u.second] == cur &&
            !used[u.first - 1][u.second]) {
          used[u.first - 1][u.second] = true;
          que.push({u.first - 1, u.second});
        }
        if (u.first < n - 1 && flag[u.first + 1][u.second] == cur &&
            !used[u.first + 1][u.second]) {
          used[u.first + 1][u.second] = true;
          que.push({u.first + 1, u.second});
        }
        if (u.second > 0 && flag[u.first][u.second - 1] == cur &&
            !used[u.first][u.second - 1]) {
          used[u.first][u.second - 1] = true;
          que.push({u.first, u.second - 1});
        }
        if (u.second < m - 1 && flag[u.first][u.second + 1] == cur &&
            !used[u.first][u.second + 1]) {
          used[u.first][u.second + 1] = true;
          que.push({u.first, u.second + 1});
        }
      }
      num++;
    }
  build(0, 0, m - 1);
  for (int i = (0), __i = (q); i < __i; i++) {
    int l, r;
    cin >> l >> r;
    cout << get_res(0, 0, m - 1, l - 1, r - 1).comps << endl;
  }
  return 0;
}

### 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;
template <class T>
ostream &operator<<(ostream &os, const vector<T> &vec) {
  os << '{';
  for (int i = (0), __i = (((int)(vec).size())); i < __i; i++) {
    os << vec[i];
    if (i + 1 != ((int)(vec).size())) os << ',';
  }
  os << '}';
  return os;
}
template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &par) {
  os << '(' << par.first << ',' << par.second << ')';
  return os;
}
int gcd(int x, int y) { return y ? gcd(y, x % y) : abs(x); }
template <class T>
T sqr(T x) {
  return x * x;
}
int n, m, q;
int flag[10][100000];
struct Vert {
  int left[10];
  int right[10];
  int comps;
};
Vert tree[400000];
bool used[10][100000];
int mask[1000000];
int numb = 0;
Vert combine(Vert v1, Vert v2) {
  Vert v;
  bool f = false;
  int stitch = 0;
  for (int i = (0), __i = (n); i < __i; i++) {
    if (mask[v1.right[i]] == mask[v2.left[i]] && v1.right[i] != v2.left[i]) {
      int nn = v2.left[i];
      for (int j = (0), __j = (n); j < __j; j++) {
        if (v1.left[j] == nn) v1.left[j] = v1.right[i];
        if (v1.right[j] == nn) v1.right[j] = v1.right[i];
        if (v2.left[j] == nn) v2.left[j] = v1.right[i];
        if (v2.right[j] == nn) v2.right[j] = v1.right[i];
      }
      stitch++;
    }
  }
  for (int i = (0), __i = (n); i < __i; i++) {
    v.left[i] = v1.left[i];
    v.right[i] = v2.right[i];
  }
  v.comps = v1.comps + v2.comps - stitch;
  return v;
}
void build(int v, int l, int r) {
  if (l == r) {
    int cur;
    for (int i = (0), __i = (n); i < __i; i++) {
      if (i == 0 || flag[i - 1][l] != flag[i][l]) {
        cur = numb++;
        mask[cur] = flag[i][l];
        tree[v].comps++;
      }
      tree[v].left[i] = tree[v].right[i] = cur;
    }
    return;
  }
  int mid = (l + r) / 2;
  build(2 * v + 1, l, mid);
  build(2 * v + 2, mid + 1, r);
  tree[v] = combine(tree[2 * v + 1], tree[2 * v + 2]);
}
Vert get_res(int v, int tl, int tr, int l, int r) {
  if (tl == l && tr == r) return tree[v];
  int mid = (tl + tr) / 2;
  if (l > mid) return get_res(2 * v + 2, mid + 1, tr, l, r);
  if (r <= mid) return get_res(2 * v + 1, tl, mid, l, r);
  Vert v1 = get_res(2 * v + 1, tl, mid, l, mid);
  Vert v2 = get_res(2 * v + 2, mid + 1, tr, mid + 1, r);
  return combine(v1, v2);
}
int main() {
  ios::sync_with_stdio(false);
  cin >> n >> m >> q;
  for (int i = (0), __i = (n); i < __i; i++)
    for (int j = (0), __j = (m); j < __j; j++) cin >> flag[i][j];
  int num = 1000001;
  for (int i = (0), __i = (n); i < __i; i++)
    for (int j = (0), __j = (m); j < __j; j++) {
      if (used[i][j]) continue;
      int cur = flag[i][j];
      queue<pair<int, int> > que;
      que.push({i, j});
      used[i][j] = true;
      while (!que.empty()) {
        pair<int, int> u = que.front();
        que.pop();
        flag[u.first][u.second] = num;
        if (u.first > 0 && flag[u.first - 1][u.second] == cur &&
            !used[u.first - 1][u.second]) {
          used[u.first - 1][u.second] = true;
          que.push({u.first - 1, u.second});
        }
        if (u.first < n - 1 && flag[u.first + 1][u.second] == cur &&
            !used[u.first + 1][u.second]) {
          used[u.first + 1][u.second] = true;
          que.push({u.first + 1, u.second});
        }
        if (u.second > 0 && flag[u.first][u.second - 1] == cur &&
            !used[u.first][u.second - 1]) {
          used[u.first][u.second - 1] = true;
          que.push({u.first, u.second - 1});
        }
        if (u.second < m - 1 && flag[u.first][u.second + 1] == cur &&
            !used[u.first][u.second + 1]) {
          used[u.first][u.second + 1] = true;
          que.push({u.first, u.second + 1});
        }
      }
      num++;
    }
  build(0, 0, m - 1);
  for (int i = (0), __i = (q); i < __i; i++) {
    int l, r;
    cin >> l >> r;
    cout << get_res(0, 0, m - 1, l - 1, r - 1).comps << endl;
  }
  return 0;
}

```