#include <bits/stdc++.h>
using namespace std;
const int MAXR = 11;
const int MAXC = 100010;
struct Profile {
  bool empty;
  int id[MAXR][2];
  int col[MAXR][2];
  int dropped;
  Profile() {
    dropped = 0;
    empty = true;
  }
};
const int MAXV = 4 * MAXR;
struct Unique_id {
  int cookie, last_id;
  int in[MAXV], id[MAXV];
  void init(void) {
    last_id = 0;
    ++cookie;
  }
  int get(int x) {
    if (in[x] != cookie) {
      id[x] = last_id++;
      in[x] = cookie;
    }
    return id[x];
  }
  bool has_id(int x) { return in[x] == cookie; }
};
int n, m, q;
int A[MAXR][MAXC];
int dad[4 * MAXR];
void clear(void) {
  for (int i = (0); i < (4 * n); ++i) dad[i] = -1;
}
int find(int x) { return dad[x] == -1 ? x : dad[x] = find(dad[x]); }
void merge(int x, int y) {
  int a = find(x), b = find(y);
  if (a != b) dad[a] = b;
}
void merge_profiles(Profile &L, Profile &R, Profile &ret) {
  if (L.empty && R.empty) {
    ret.empty = true;
    ret.dropped = 0;
    return;
  }
  ret.empty = false;
  if (L.empty || R.empty) {
    ret = L.empty ? R : L;
    return;
  }
  for (int i = (0); i < (4 * n); ++i) dad[i] = -1;
  for (int i = (0); i < (n); ++i) {
    if (L.col[i][1] == R.col[i][0]) merge(L.id[i][1], 2 * n + R.id[i][0]);
  }
  static Unique_id UID;
  UID.init();
  for (int i = (0); i < (n); ++i) {
    ret.col[i][0] = L.col[i][0];
    ret.col[i][1] = R.col[i][1];
    ret.id[i][0] = UID.get(find(L.id[i][0]));
    ret.id[i][1] = UID.get(find(2 * n + R.id[i][1]));
  }
  ret.dropped = L.dropped + R.dropped;
  for (int i = (0); i < (n); ++i) {
    ret.dropped += !UID.has_id(find(L.id[i][1]));
    UID.get(find(L.id[i][1]));
    ret.dropped += !UID.has_id(find(2 * n + R.id[i][0]));
    UID.get(find(2 * n + R.id[i][0]));
  }
}
void profile_from_col(int col, Profile &ret) {
  int last_id = 0;
  ret.empty = false;
  ret.dropped = 0;
  for (int i = (0); i < (n); ++i) {
    ret.col[i][0] = ret.col[i][1] = A[i][col];
    if (i > 0 && A[i][col] != A[i - 1][col]) last_id++;
    ret.id[i][0] = ret.id[i][1] = last_id;
  }
}
const int OFFSET = 1 << 17;
Profile P[2 * OFFSET];
void build(void) {
  for (int i = (0); i < (m); ++i) profile_from_col(i, P[OFFSET + i]);
  for (int sz = OFFSET / 2; sz > 0; sz /= 2)
    for (int i = sz; i < 2 * sz; ++i)
      merge_profiles(P[2 * i], P[2 * i + 1], P[i]);
}
int from, to;
void get(int t, int lo, int hi, Profile &ret) {
  if (lo >= to || hi <= from) {
    ret.empty = true;
    ret.dropped = 0;
    return;
  }
  if (lo >= from && hi <= to) {
    ret = P[t];
    return;
  }
  Profile L, R;
  get(2 * t, lo, (lo + hi) / 2, L);
  get(2 * t + 1, (lo + hi) / 2, hi, R);
  merge_profiles(L, R, ret);
}
void print_profile(const Profile &p) {
  if (p.empty) {
    printf("empty\n");
    return;
  }
  fprintf(stderr, "dropped = %d\n", p.dropped);
  for (int i = (0); i < (n); ++i) {
    for (int j = (0); j < (2); ++j)
      fprintf(stderr, "(%d, %d) ", p.id[i][j], p.col[i][j]);
    fprintf(stderr, "\n");
  }
}
int count(const Profile &p) {
  static Unique_id UID;
  UID.init();
  int ret = p.dropped;
  for (int i = (0); i < (n); ++i)
    for (int j = (0); j < (2); ++j) {
      ret += !UID.has_id(p.id[i][j]);
      UID.get(p.id[i][j]);
    }
  return ret;
}
int query(int l, int r) {
  Profile T;
  from = l;
  to = r + 1;
  get(1, 0, OFFSET, T);
  return count(T);
}
int main(void) {
  scanf("%d%d%d", &n, &m, &q);
  for (int i = (0); i < (n); ++i)
    for (int j = (0); j < (m); ++j) scanf("%d", &A[i][j]);
  build();
  for (int i = (0); i < (q); ++i) {
    int l, r;
    scanf("%d%d", &l, &r);
    --l, --r;
    printf("%d\n", query(l, r));
  }
  return 0;
}

### Prompt

Generate 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;
const int MAXR = 11;
const int MAXC = 100010;
struct Profile {
  bool empty;
  int id[MAXR][2];
  int col[MAXR][2];
  int dropped;
  Profile() {
    dropped = 0;
    empty = true;
  }
};
const int MAXV = 4 * MAXR;
struct Unique_id {
  int cookie, last_id;
  int in[MAXV], id[MAXV];
  void init(void) {
    last_id = 0;
    ++cookie;
  }
  int get(int x) {
    if (in[x] != cookie) {
      id[x] = last_id++;
      in[x] = cookie;
    }
    return id[x];
  }
  bool has_id(int x) { return in[x] == cookie; }
};
int n, m, q;
int A[MAXR][MAXC];
int dad[4 * MAXR];
void clear(void) {
  for (int i = (0); i < (4 * n); ++i) dad[i] = -1;
}
int find(int x) { return dad[x] == -1 ? x : dad[x] = find(dad[x]); }
void merge(int x, int y) {
  int a = find(x), b = find(y);
  if (a != b) dad[a] = b;
}
void merge_profiles(Profile &L, Profile &R, Profile &ret) {
  if (L.empty && R.empty) {
    ret.empty = true;
    ret.dropped = 0;
    return;
  }
  ret.empty = false;
  if (L.empty || R.empty) {
    ret = L.empty ? R : L;
    return;
  }
  for (int i = (0); i < (4 * n); ++i) dad[i] = -1;
  for (int i = (0); i < (n); ++i) {
    if (L.col[i][1] == R.col[i][0]) merge(L.id[i][1], 2 * n + R.id[i][0]);
  }
  static Unique_id UID;
  UID.init();
  for (int i = (0); i < (n); ++i) {
    ret.col[i][0] = L.col[i][0];
    ret.col[i][1] = R.col[i][1];
    ret.id[i][0] = UID.get(find(L.id[i][0]));
    ret.id[i][1] = UID.get(find(2 * n + R.id[i][1]));
  }
  ret.dropped = L.dropped + R.dropped;
  for (int i = (0); i < (n); ++i) {
    ret.dropped += !UID.has_id(find(L.id[i][1]));
    UID.get(find(L.id[i][1]));
    ret.dropped += !UID.has_id(find(2 * n + R.id[i][0]));
    UID.get(find(2 * n + R.id[i][0]));
  }
}
void profile_from_col(int col, Profile &ret) {
  int last_id = 0;
  ret.empty = false;
  ret.dropped = 0;
  for (int i = (0); i < (n); ++i) {
    ret.col[i][0] = ret.col[i][1] = A[i][col];
    if (i > 0 && A[i][col] != A[i - 1][col]) last_id++;
    ret.id[i][0] = ret.id[i][1] = last_id;
  }
}
const int OFFSET = 1 << 17;
Profile P[2 * OFFSET];
void build(void) {
  for (int i = (0); i < (m); ++i) profile_from_col(i, P[OFFSET + i]);
  for (int sz = OFFSET / 2; sz > 0; sz /= 2)
    for (int i = sz; i < 2 * sz; ++i)
      merge_profiles(P[2 * i], P[2 * i + 1], P[i]);
}
int from, to;
void get(int t, int lo, int hi, Profile &ret) {
  if (lo >= to || hi <= from) {
    ret.empty = true;
    ret.dropped = 0;
    return;
  }
  if (lo >= from && hi <= to) {
    ret = P[t];
    return;
  }
  Profile L, R;
  get(2 * t, lo, (lo + hi) / 2, L);
  get(2 * t + 1, (lo + hi) / 2, hi, R);
  merge_profiles(L, R, ret);
}
void print_profile(const Profile &p) {
  if (p.empty) {
    printf("empty\n");
    return;
  }
  fprintf(stderr, "dropped = %d\n", p.dropped);
  for (int i = (0); i < (n); ++i) {
    for (int j = (0); j < (2); ++j)
      fprintf(stderr, "(%d, %d) ", p.id[i][j], p.col[i][j]);
    fprintf(stderr, "\n");
  }
}
int count(const Profile &p) {
  static Unique_id UID;
  UID.init();
  int ret = p.dropped;
  for (int i = (0); i < (n); ++i)
    for (int j = (0); j < (2); ++j) {
      ret += !UID.has_id(p.id[i][j]);
      UID.get(p.id[i][j]);
    }
  return ret;
}
int query(int l, int r) {
  Profile T;
  from = l;
  to = r + 1;
  get(1, 0, OFFSET, T);
  return count(T);
}
int main(void) {
  scanf("%d%d%d", &n, &m, &q);
  for (int i = (0); i < (n); ++i)
    for (int j = (0); j < (m); ++j) scanf("%d", &A[i][j]);
  build();
  for (int i = (0); i < (q); ++i) {
    int l, r;
    scanf("%d%d", &l, &r);
    --l, --r;
    printf("%d\n", query(l, r));
  }
  return 0;
}

```