#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 10, MN = 1e5 + 10, MV = 2e6 + 10;
struct node {
  pair<int, int> R[10], L[10];
  int C;
  node() {
    for (int i = 0; i < 10; ++i) L[i] = R[i] = {-1, -1};
    C = 0;
  }
} seg[MN << 2];
unordered_set<long long> M;
int n, k;
int arr[12][MN];
int par[MV];
int root(int a) {
  if (par[a] == a) return a;
  return par[a] = root(par[a]);
}
void Union(int a, int b) {
  a = root(a), b = root(b);
  if (a == b) return;
  par[b] = a;
}
node mrg(node A, node B) {
  if (A.C == 0) return B;
  if (B.C == 0) return A;
  node ret;
  ret.C = A.C + B.C;
  for (int i = 0; i < k; ++i) {
    if (A.R[i].second == B.L[i].second) {
      Union(2 * A.R[i].first + 1, 2 * B.L[i].first);
      M.insert(1ll * A.R[i].first * INF + 1ll * B.L[i].first);
    }
  }
  ret.C -= ((int)(M).size());
  M.clear();
  for (int i = 0; i < k; ++i) {
    ret.L[i] = {root(2 * A.L[i].first + 1), A.L[i].second};
    ret.R[i] = {root(2 * B.R[i].first), B.R[i].second};
  }
  for (int i = 0; i < k; ++i) {
    int x = 2 * A.R[i].first + 1, y = 2 * B.L[i].first;
    par[x] = x, par[y] = y;
  }
  return ret;
}
void build(int id, int b, int e) {
  if (e - b == 1) {
    int tmp = 0;
    for (int i = 0; i < k; ++i) {
      if (i && arr[i][b] != arr[i - 1][b])
        seg[id].L[i] = seg[id].R[i] = {++tmp, arr[i][b]};
      else
        seg[id].R[i] = seg[id].L[i] = {tmp, arr[i][b]};
      seg[id].C = tmp + 1;
    }
    return;
  }
  int mid = b + e >> 1;
  build(id << 1, b, mid), build(id << 1 | 1, mid, e);
  seg[id] = mrg(seg[id << 1], seg[id << 1 | 1]);
}
node get(int id, int b, int e, int l, int r) {
  if (r <= b || e <= l) return node();
  if (l <= b && e <= r) return seg[id];
  int mid = b + e >> 1;
  return mrg(get(id << 1, b, mid, l, r), get(id << 1 | 1, mid, e, l, r));
}
int main() {
  ios_base ::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  for (int i = 0; i < MV; ++i) par[i] = i;
  int q;
  scanf("%d%d%d", &k, &n, &q);
  for (int i = 0; i < k; ++i)
    for (int j = 0; j < n; ++j) scanf("%d", &arr[i][j]);
  build(1, 0, n);
  while (q--) {
    int l, r;
    scanf("%d%d", &l, &r);
    printf("%d\n", get(1, 0, n, l - 1, r).C);
  }
  return 0;
}

### Prompt

Construct a Cpp code solution to the problem outlined:

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 INF = 1e9 + 10, MN = 1e5 + 10, MV = 2e6 + 10;
struct node {
  pair<int, int> R[10], L[10];
  int C;
  node() {
    for (int i = 0; i < 10; ++i) L[i] = R[i] = {-1, -1};
    C = 0;
  }
} seg[MN << 2];
unordered_set<long long> M;
int n, k;
int arr[12][MN];
int par[MV];
int root(int a) {
  if (par[a] == a) return a;
  return par[a] = root(par[a]);
}
void Union(int a, int b) {
  a = root(a), b = root(b);
  if (a == b) return;
  par[b] = a;
}
node mrg(node A, node B) {
  if (A.C == 0) return B;
  if (B.C == 0) return A;
  node ret;
  ret.C = A.C + B.C;
  for (int i = 0; i < k; ++i) {
    if (A.R[i].second == B.L[i].second) {
      Union(2 * A.R[i].first + 1, 2 * B.L[i].first);
      M.insert(1ll * A.R[i].first * INF + 1ll * B.L[i].first);
    }
  }
  ret.C -= ((int)(M).size());
  M.clear();
  for (int i = 0; i < k; ++i) {
    ret.L[i] = {root(2 * A.L[i].first + 1), A.L[i].second};
    ret.R[i] = {root(2 * B.R[i].first), B.R[i].second};
  }
  for (int i = 0; i < k; ++i) {
    int x = 2 * A.R[i].first + 1, y = 2 * B.L[i].first;
    par[x] = x, par[y] = y;
  }
  return ret;
}
void build(int id, int b, int e) {
  if (e - b == 1) {
    int tmp = 0;
    for (int i = 0; i < k; ++i) {
      if (i && arr[i][b] != arr[i - 1][b])
        seg[id].L[i] = seg[id].R[i] = {++tmp, arr[i][b]};
      else
        seg[id].R[i] = seg[id].L[i] = {tmp, arr[i][b]};
      seg[id].C = tmp + 1;
    }
    return;
  }
  int mid = b + e >> 1;
  build(id << 1, b, mid), build(id << 1 | 1, mid, e);
  seg[id] = mrg(seg[id << 1], seg[id << 1 | 1]);
}
node get(int id, int b, int e, int l, int r) {
  if (r <= b || e <= l) return node();
  if (l <= b && e <= r) return seg[id];
  int mid = b + e >> 1;
  return mrg(get(id << 1, b, mid, l, r), get(id << 1 | 1, mid, e, l, r));
}
int main() {
  ios_base ::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  for (int i = 0; i < MV; ++i) par[i] = i;
  int q;
  scanf("%d%d%d", &k, &n, &q);
  for (int i = 0; i < k; ++i)
    for (int j = 0; j < n; ++j) scanf("%d", &arr[i][j]);
  build(1, 0, n);
  while (q--) {
    int l, r;
    scanf("%d%d", &l, &r);
    printf("%d\n", get(1, 0, n, l - 1, r).C);
  }
  return 0;
}

```