#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXM = 1 << 18;
const int MAXN = 11;
int par[MAXM * 10], cnt;
int find_root(int x) {
  if (par[x] == x)
    return x;
  else
    return par[x] = find_root(par[x]);
}
void unite(int x, int y) {
  x = find_root(x), y = find_root(y);
  if (x == y) return;
  par[x] = y;
}
struct Node {
  int L[MAXN], R[MAXN];
  int C;
} ST[MAXM];
int n, m;
int flag[MAXN][MAXM];
Node Merge(Node a, Node b, int l, int m, int r) {
  if (a.C == 0) return b;
  if (b.C == 0) return a;
  Node res;
  res.C = a.C + b.C;
  for (int i = (0); i < (n); i++)
    par[a.R[i]] = a.R[i], par[a.L[i]] = a.L[i], par[b.L[i]] = b.L[i],
    par[b.R[i]] = b.R[i];
  for (int i = (0); i < (n); i++) {
    if (flag[i][m - 1] == flag[i][m]) {
      if (find_root(a.R[i]) != find_root(b.L[i])) res.C--;
      unite(a.R[i], b.L[i]);
    }
  }
  for (int i = (0); i < (n); i++)
    res.R[i] = find_root(b.R[i]), res.L[i] = find_root(a.L[i]);
  return res;
}
void build(int k, int l, int r) {
  if (r - l == 0) return;
  if (r - l == 1) {
    for (int i = (0); i < (n); i++) ST[k].L[i] = cnt++;
    for (int i = (0); i < (n); i++) par[ST[k].L[i]] = ST[k].L[i];
    for (int i = (1); i < (n); i++) {
      if (flag[i - 1][l] == flag[i][l]) unite(ST[k].L[i], ST[k].L[i - 1]);
    }
    for (int i = (0); i < (n); i++) {
      if (ST[k].L[i] == find_root(ST[k].L[i])) ST[k].C++;
      ST[k].L[i] = ST[k].R[i] = find_root(ST[k].L[i]);
    }
    return;
  }
  int m = l + r >> 1;
  build((k << 1), l, m);
  build((k << 1 | 1), m, r);
  ST[k] = Merge(ST[(k << 1)], ST[(k << 1 | 1)], l, m, r);
}
Node query(int k, int l, int r, int ql, int qr) {
  if (ql >= r || qr <= l) {
    Node res;
    res.C = 0;
    return res;
  }
  if (ql <= l && r <= qr) return ST[k];
  int m = l + r >> 1;
  return Merge(query((k << 1), l, m, ql, qr), query((k << 1 | 1), m, r, ql, qr),
               l, m, r);
}
int main() {
  int q;
  scanf("%d%d%d", &n, &m, &q);
  for (int i = (0); i < (n); i++)
    for (int j = (1); j < (m + 1); j++) scanf("%d", &flag[i][j]);
  build(1, 1, m + 1);
  for (int i = (0); i < (q); i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    Node Q = query(1, 1, m + 1, l, r + 1);
    printf("%d\n", Q.C);
  }
}

### Prompt

Please formulate 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 INF = 0x3f3f3f3f;
const int MAXM = 1 << 18;
const int MAXN = 11;
int par[MAXM * 10], cnt;
int find_root(int x) {
  if (par[x] == x)
    return x;
  else
    return par[x] = find_root(par[x]);
}
void unite(int x, int y) {
  x = find_root(x), y = find_root(y);
  if (x == y) return;
  par[x] = y;
}
struct Node {
  int L[MAXN], R[MAXN];
  int C;
} ST[MAXM];
int n, m;
int flag[MAXN][MAXM];
Node Merge(Node a, Node b, int l, int m, int r) {
  if (a.C == 0) return b;
  if (b.C == 0) return a;
  Node res;
  res.C = a.C + b.C;
  for (int i = (0); i < (n); i++)
    par[a.R[i]] = a.R[i], par[a.L[i]] = a.L[i], par[b.L[i]] = b.L[i],
    par[b.R[i]] = b.R[i];
  for (int i = (0); i < (n); i++) {
    if (flag[i][m - 1] == flag[i][m]) {
      if (find_root(a.R[i]) != find_root(b.L[i])) res.C--;
      unite(a.R[i], b.L[i]);
    }
  }
  for (int i = (0); i < (n); i++)
    res.R[i] = find_root(b.R[i]), res.L[i] = find_root(a.L[i]);
  return res;
}
void build(int k, int l, int r) {
  if (r - l == 0) return;
  if (r - l == 1) {
    for (int i = (0); i < (n); i++) ST[k].L[i] = cnt++;
    for (int i = (0); i < (n); i++) par[ST[k].L[i]] = ST[k].L[i];
    for (int i = (1); i < (n); i++) {
      if (flag[i - 1][l] == flag[i][l]) unite(ST[k].L[i], ST[k].L[i - 1]);
    }
    for (int i = (0); i < (n); i++) {
      if (ST[k].L[i] == find_root(ST[k].L[i])) ST[k].C++;
      ST[k].L[i] = ST[k].R[i] = find_root(ST[k].L[i]);
    }
    return;
  }
  int m = l + r >> 1;
  build((k << 1), l, m);
  build((k << 1 | 1), m, r);
  ST[k] = Merge(ST[(k << 1)], ST[(k << 1 | 1)], l, m, r);
}
Node query(int k, int l, int r, int ql, int qr) {
  if (ql >= r || qr <= l) {
    Node res;
    res.C = 0;
    return res;
  }
  if (ql <= l && r <= qr) return ST[k];
  int m = l + r >> 1;
  return Merge(query((k << 1), l, m, ql, qr), query((k << 1 | 1), m, r, ql, qr),
               l, m, r);
}
int main() {
  int q;
  scanf("%d%d%d", &n, &m, &q);
  for (int i = (0); i < (n); i++)
    for (int j = (1); j < (m + 1); j++) scanf("%d", &flag[i][j]);
  build(1, 1, m + 1);
  for (int i = (0); i < (q); i++) {
    int l, r;
    scanf("%d%d", &l, &r);
    Node Q = query(1, 1, m + 1, l, r + 1);
    printf("%d\n", Q.C);
  }
}

```