#include <bits/stdc++.h>
using namespace std;
int tu(int val) { return (1 << val); }
bool iset(int mask, int id) {
  if ((mask & tu(id)) != 0) return true;
  return false;
}
void doset(int &mask, int id) { mask |= tu(id); }
void dounset(int &mask, int id) { mask = mask & (~tu(id)); }
template <typename T>
string tos(T a) {
  stringstream ss;
  string ret;
  ss << a;
  ss >> ret;
  return ret;
}
int n, m;
struct node {
  pair<int, int> pre[10], nxt[10];
  int cnt;
  void domin(int x, int y) {
    --cnt;
    for (int(i) = (0); (i) < (n); (i)++) {
      if (pre[i].second == x) pre[i].second = y;
      if (nxt[i].second == x) nxt[i].second = y;
    }
  }
};
node merge(node a, node b) {
  node ret;
  ret.cnt = a.cnt + b.cnt;
  for (int(i) = (0); (i) < (n); (i)++) {
    ret.pre[i] = a.pre[i];
    ret.nxt[i] = b.nxt[i];
  }
  set<pair<int, int> > st;
  for (int(i) = (0); (i) < (n); (i)++)
    if (a.nxt[i].first == b.pre[i].first &&
        a.nxt[i].second != b.pre[i].second) {
      int va = a.nxt[i].second;
      int vb = b.pre[i].second;
      pair<int, int> nw = make_pair(va, vb);
      if (st.count(nw)) continue;
      st.insert(nw);
      ret.domin(va, vb);
      a.domin(va, vb);
    }
  return ret;
};
node tx[262144];
int ar[10][100000], gv;
void build(int t = 1, int l = 0, int r = m - 1) {
  if (l == r) {
    for (int(i) = (0); (i) < (n); (i)++) {
      if (i && ar[i][l] == ar[i - 1][l]) {
        tx[t].pre[i] = tx[t].nxt[i] = tx[t].pre[i - 1];
      } else {
        tx[t].cnt++;
        tx[t].pre[i] = tx[t].nxt[i] = make_pair(ar[i][l], ++gv);
      }
    }
    return;
  }
  int m = (l + r) / 2;
  build(t + t, l, m);
  build(t + t + 1, m + 1, r);
  tx[t] = merge(tx[t + t], tx[t + t + 1]);
}
node get(int ll, int rr, int t = 1, int l = 0, int r = m - 1) {
  if (l >= ll & r <= rr) return tx[t];
  int m = (l + r) / 2;
  if (rr <= m) return get(ll, rr, t + t, l, m);
  if (ll > m) return get(ll, rr, t + t + 1, m + 1, r);
  node a = get(ll, m, t + t, l, m);
  node b = get(m + 1, rr, t + t + 1, m + 1, r);
  return merge(a, b);
}
int main() {
  int q;
  while (scanf("%d %d %d", &n, &m, &q) == 3) {
    gv = 0;
    for (int(i) = (0); (i) < (n); (i)++)
      for (int(j) = (0); (j) < (m); (j)++) scanf("%d", &ar[i][j]);
    build();
    for (int(i) = (0); (i) < (q); (i)++) {
      int va, vb;
      scanf("%d %d", &va, &vb);
      va--;
      vb--;
      node ans = get(va, vb);
      printf("%d\n", ans.cnt);
    }
  }
  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;
int tu(int val) { return (1 << val); }
bool iset(int mask, int id) {
  if ((mask & tu(id)) != 0) return true;
  return false;
}
void doset(int &mask, int id) { mask |= tu(id); }
void dounset(int &mask, int id) { mask = mask & (~tu(id)); }
template <typename T>
string tos(T a) {
  stringstream ss;
  string ret;
  ss << a;
  ss >> ret;
  return ret;
}
int n, m;
struct node {
  pair<int, int> pre[10], nxt[10];
  int cnt;
  void domin(int x, int y) {
    --cnt;
    for (int(i) = (0); (i) < (n); (i)++) {
      if (pre[i].second == x) pre[i].second = y;
      if (nxt[i].second == x) nxt[i].second = y;
    }
  }
};
node merge(node a, node b) {
  node ret;
  ret.cnt = a.cnt + b.cnt;
  for (int(i) = (0); (i) < (n); (i)++) {
    ret.pre[i] = a.pre[i];
    ret.nxt[i] = b.nxt[i];
  }
  set<pair<int, int> > st;
  for (int(i) = (0); (i) < (n); (i)++)
    if (a.nxt[i].first == b.pre[i].first &&
        a.nxt[i].second != b.pre[i].second) {
      int va = a.nxt[i].second;
      int vb = b.pre[i].second;
      pair<int, int> nw = make_pair(va, vb);
      if (st.count(nw)) continue;
      st.insert(nw);
      ret.domin(va, vb);
      a.domin(va, vb);
    }
  return ret;
};
node tx[262144];
int ar[10][100000], gv;
void build(int t = 1, int l = 0, int r = m - 1) {
  if (l == r) {
    for (int(i) = (0); (i) < (n); (i)++) {
      if (i && ar[i][l] == ar[i - 1][l]) {
        tx[t].pre[i] = tx[t].nxt[i] = tx[t].pre[i - 1];
      } else {
        tx[t].cnt++;
        tx[t].pre[i] = tx[t].nxt[i] = make_pair(ar[i][l], ++gv);
      }
    }
    return;
  }
  int m = (l + r) / 2;
  build(t + t, l, m);
  build(t + t + 1, m + 1, r);
  tx[t] = merge(tx[t + t], tx[t + t + 1]);
}
node get(int ll, int rr, int t = 1, int l = 0, int r = m - 1) {
  if (l >= ll & r <= rr) return tx[t];
  int m = (l + r) / 2;
  if (rr <= m) return get(ll, rr, t + t, l, m);
  if (ll > m) return get(ll, rr, t + t + 1, m + 1, r);
  node a = get(ll, m, t + t, l, m);
  node b = get(m + 1, rr, t + t + 1, m + 1, r);
  return merge(a, b);
}
int main() {
  int q;
  while (scanf("%d %d %d", &n, &m, &q) == 3) {
    gv = 0;
    for (int(i) = (0); (i) < (n); (i)++)
      for (int(j) = (0); (j) < (m); (j)++) scanf("%d", &ar[i][j]);
    build();
    for (int(i) = (0); (i) < (q); (i)++) {
      int va, vb;
      scanf("%d %d", &va, &vb);
      va--;
      vb--;
      node ans = get(va, vb);
      printf("%d\n", ans.cnt);
    }
  }
  return 0;
}

```