#include <bits/stdc++.h>
using namespace std;
bool RELAXED = false;
template <int, typename T>
struct MINMAX {
  T val;
  MINMAX(T val) : val(val) {}
};
template <typename T>
MINMAX<1, T> MAX(T val) {
  return MINMAX<1, T>(val);
};
template <typename T>
MINMAX<2, T> MIN(T val) {
  return MINMAX<2, T>(val);
};
template <typename T, typename U>
inline T& operator|=(T& lhs, MINMAX<1, U> rhs) {
  return lhs = (rhs.val > lhs ? (RELAXED = true, rhs.val)
                              : (RELAXED = false, lhs));
}
template <typename T, typename U>
inline T& operator|=(T& lhs, MINMAX<2, U> rhs) {
  return lhs = (rhs.val < lhs ? (RELAXED = true, rhs.val)
                              : (RELAXED = false, lhs));
}
template <typename T>
inline vector<T> readVector(int n) {
  vector<T> vec(n);
  for (int i = 0; i < int(n); i++) cin >> vec[i];
  return vec;
}
template <typename T>
void EXIT(T answer) {
  cout << answer << endl;
  exit(0);
}
const int MAXM = 1e5 + 5;
int A[12][MAXM];
int N;
struct DisjointSet {
  int parent[64];
  bool lastMerge = false;
  void makeSet(int v) { parent[v] = v; }
  int root(int v) { return parent[v] == v ? v : (parent[v] = root(parent[v])); }
  void merge(int x, int y) {
    x = root(x);
    y = root(y);
    lastMerge = x != y;
    if (x == y) return;
    parent[y] = x;
  }
};
DisjointSet ds;
struct Area {
  int lc, rc;
  int count = 0;
  int lcomp[12], rcomp[12];
  void init(int col) {
    lc = rc = col;
    count = N;
    for (int i = 0; i < int(N); i++) lcomp[i] = rcomp[i] = i + 1;
    for (int i = 0; i < int(N - 1); i++) {
      if (A[i][col] == A[i + 1][col]) {
        lcomp[i + 1] = rcomp[i + 1] = lcomp[i];
        count--;
      }
    }
  }
  void merge(Area left, Area right) {
    for (int i = 0; i < int(N); i++) {
      ds.makeSet(left.lcomp[i]);
      ds.makeSet(left.rcomp[i]);
      ds.makeSet(right.lcomp[i] + 30);
      ds.makeSet(right.rcomp[i] + 30);
    }
    for (int i = 0; i < int(N); i++) {
      if (A[i][left.rc] == A[i][right.lc]) {
        ds.merge(left.rcomp[i], right.lcomp[i] + 30);
        if (ds.lastMerge) count--;
      }
    }
    lc = left.lc;
    rc = right.rc;
    count += left.count + right.count;
    int id[64] = {0};
    for (int i = 0; i < int(N); i++) {
      int comp = ds.root(left.lcomp[i]);
      if (id[comp] == 0) id[comp] = i + 1;
      lcomp[i] = id[comp];
    }
    for (int i = 0; i < int(N); i++) {
      int comp = ds.root(right.rcomp[i] + 30);
      if (id[comp] == 0) id[comp] = N + i + 1;
      rcomp[i] = id[comp];
    }
  }
};
struct SegTree {
  static const int INF = 1 << 30;
  static const int H = 17;
  static const int N = 1 << H;
  Area t[2 * N];

 private:
  void recompute(int ID) { t[ID].merge(t[(ID << 1)], t[(ID << 1 | 1)]); }
  void propagate(int ID) {}

 public:
  void build(int ID = 1, int L = 0, int R = N - 1) {
    if (L == R) {
      t[ID].init(L);
      return;
    }
    propagate(ID);
    int mid = L + (R - L) / 2;
    build(ID * 2, L, mid);
    build(ID * 2 + 1, mid + 1, R);
    recompute(ID);
  }
  Area query(int from, int to, int ID = 1, int L = 0, int R = N - 1) {
    if (from <= L && to >= R) return t[ID];
    propagate(ID);
    int res = INF;
    int mid = L + (R - L) / 2;
    if (to <= mid) return query(from, to, ID * 2, L, mid);
    if (from >= mid + 1) return query(from, to, ID * 2 + 1, mid + 1, R);
    Area area;
    area.merge(query(from, to, ID * 2, L, mid),
               query(from, to, ID * 2 + 1, mid + 1, R));
    return area;
  }
};
SegTree st;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n, m, q;
  cin >> n >> m >> q;
  for (int i = 0; i < int(n); i++)
    for (int j = 0; j < int(m); j++) cin >> A[i][j];
  N = n;
  st.build();
  for (int i = 0; i < int(q); i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    cout << st.query(a, b).count << '\n';
  }
  return 0;
}

### Prompt

Your challenge is to write 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;
bool RELAXED = false;
template <int, typename T>
struct MINMAX {
  T val;
  MINMAX(T val) : val(val) {}
};
template <typename T>
MINMAX<1, T> MAX(T val) {
  return MINMAX<1, T>(val);
};
template <typename T>
MINMAX<2, T> MIN(T val) {
  return MINMAX<2, T>(val);
};
template <typename T, typename U>
inline T& operator|=(T& lhs, MINMAX<1, U> rhs) {
  return lhs = (rhs.val > lhs ? (RELAXED = true, rhs.val)
                              : (RELAXED = false, lhs));
}
template <typename T, typename U>
inline T& operator|=(T& lhs, MINMAX<2, U> rhs) {
  return lhs = (rhs.val < lhs ? (RELAXED = true, rhs.val)
                              : (RELAXED = false, lhs));
}
template <typename T>
inline vector<T> readVector(int n) {
  vector<T> vec(n);
  for (int i = 0; i < int(n); i++) cin >> vec[i];
  return vec;
}
template <typename T>
void EXIT(T answer) {
  cout << answer << endl;
  exit(0);
}
const int MAXM = 1e5 + 5;
int A[12][MAXM];
int N;
struct DisjointSet {
  int parent[64];
  bool lastMerge = false;
  void makeSet(int v) { parent[v] = v; }
  int root(int v) { return parent[v] == v ? v : (parent[v] = root(parent[v])); }
  void merge(int x, int y) {
    x = root(x);
    y = root(y);
    lastMerge = x != y;
    if (x == y) return;
    parent[y] = x;
  }
};
DisjointSet ds;
struct Area {
  int lc, rc;
  int count = 0;
  int lcomp[12], rcomp[12];
  void init(int col) {
    lc = rc = col;
    count = N;
    for (int i = 0; i < int(N); i++) lcomp[i] = rcomp[i] = i + 1;
    for (int i = 0; i < int(N - 1); i++) {
      if (A[i][col] == A[i + 1][col]) {
        lcomp[i + 1] = rcomp[i + 1] = lcomp[i];
        count--;
      }
    }
  }
  void merge(Area left, Area right) {
    for (int i = 0; i < int(N); i++) {
      ds.makeSet(left.lcomp[i]);
      ds.makeSet(left.rcomp[i]);
      ds.makeSet(right.lcomp[i] + 30);
      ds.makeSet(right.rcomp[i] + 30);
    }
    for (int i = 0; i < int(N); i++) {
      if (A[i][left.rc] == A[i][right.lc]) {
        ds.merge(left.rcomp[i], right.lcomp[i] + 30);
        if (ds.lastMerge) count--;
      }
    }
    lc = left.lc;
    rc = right.rc;
    count += left.count + right.count;
    int id[64] = {0};
    for (int i = 0; i < int(N); i++) {
      int comp = ds.root(left.lcomp[i]);
      if (id[comp] == 0) id[comp] = i + 1;
      lcomp[i] = id[comp];
    }
    for (int i = 0; i < int(N); i++) {
      int comp = ds.root(right.rcomp[i] + 30);
      if (id[comp] == 0) id[comp] = N + i + 1;
      rcomp[i] = id[comp];
    }
  }
};
struct SegTree {
  static const int INF = 1 << 30;
  static const int H = 17;
  static const int N = 1 << H;
  Area t[2 * N];

 private:
  void recompute(int ID) { t[ID].merge(t[(ID << 1)], t[(ID << 1 | 1)]); }
  void propagate(int ID) {}

 public:
  void build(int ID = 1, int L = 0, int R = N - 1) {
    if (L == R) {
      t[ID].init(L);
      return;
    }
    propagate(ID);
    int mid = L + (R - L) / 2;
    build(ID * 2, L, mid);
    build(ID * 2 + 1, mid + 1, R);
    recompute(ID);
  }
  Area query(int from, int to, int ID = 1, int L = 0, int R = N - 1) {
    if (from <= L && to >= R) return t[ID];
    propagate(ID);
    int res = INF;
    int mid = L + (R - L) / 2;
    if (to <= mid) return query(from, to, ID * 2, L, mid);
    if (from >= mid + 1) return query(from, to, ID * 2 + 1, mid + 1, R);
    Area area;
    area.merge(query(from, to, ID * 2, L, mid),
               query(from, to, ID * 2 + 1, mid + 1, R));
    return area;
  }
};
SegTree st;
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int n, m, q;
  cin >> n >> m >> q;
  for (int i = 0; i < int(n); i++)
    for (int j = 0; j < int(m); j++) cin >> A[i][j];
  N = n;
  st.build();
  for (int i = 0; i < int(q); i++) {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    cout << st.query(a, b).count << '\n';
  }
  return 0;
}

```