#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 100, M = 1e5 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline long long read() {
  char ch = getchar();
  long long f = 1, x = 0;
  while (ch > '9' || ch < '0') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
int n, m, q;
int idx;
struct node {
  int l[11], r[11], sum;
  node() {
    sum = 0;
    for (int i = 0; i < 11; i++) l[i] = r[i] = 0;
  }
} tr[N << 2];
int fa[N * 44];
int g[11][N];
int getfa(int x) { return x == fa[x] ? x : fa[x] = getfa(fa[x]); }
node mer(int mid, node l, node r) {
  node res;
  res.sum = l.sum + r.sum;
  for (int i = 1; i <= n; i++) {
    fa[l.l[i]] = l.l[i];
    fa[l.r[i]] = l.r[i];
    fa[r.l[i]] = r.l[i];
    fa[r.r[i]] = r.r[i];
  }
  for (int i = 1; i <= n; i++) {
    if (g[i][mid] == g[i][mid + 1]) {
      int xx = getfa(l.r[i]), yy = getfa(r.l[i]);
      if (xx == yy)
        continue;
      else
        fa[xx] = yy, res.sum--;
    }
  }
  for (int i = 1; i <= n; i++)
    res.l[i] = getfa(l.l[i]), res.r[i] = getfa(r.r[i]);
  return res;
}
void build(int o, int l, int r) {
  if (l == r) {
    tr[o].sum = n;
    for (int i = 1; i <= n; i++) {
      if (g[i][l] == g[i - 1][l])
        tr[o].l[i] = tr[o].r[i] = idx, tr[o].sum--;
      else
        tr[o].l[i] = tr[o].r[i] = ++idx;
    }
    return;
  }
  int mid = l + r >> 1;
  build((o << 1), l, mid);
  build((o << 1 | 1), mid + 1, r);
  tr[o] = mer(mid, tr[(o << 1)], tr[(o << 1 | 1)]);
}
node qry(int o, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr) return tr[o];
  int mid = l + r >> 1;
  if (qr <= mid)
    return qry((o << 1), l, mid, ql, qr);
  else if (mid < ql)
    return qry((o << 1 | 1), mid + 1, r, ql, qr);
  else
    return mer(mid, qry((o << 1), l, mid, ql, qr),
               qry((o << 1 | 1), mid + 1, r, ql, qr));
}
int main() {
  scanf("%d%d%d", &n, &m, &q);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) scanf("%d", &g[i][j]);
  build(1, 1, m);
  while (q--) {
    int x, y;
    scanf("%d%d", &x, &y);
    printf("%d\n", qry(1, 1, m, x, y).sum);
  }
  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 N = 1e5 + 100, M = 1e5 + 10;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline long long read() {
  char ch = getchar();
  long long f = 1, x = 0;
  while (ch > '9' || ch < '0') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
int n, m, q;
int idx;
struct node {
  int l[11], r[11], sum;
  node() {
    sum = 0;
    for (int i = 0; i < 11; i++) l[i] = r[i] = 0;
  }
} tr[N << 2];
int fa[N * 44];
int g[11][N];
int getfa(int x) { return x == fa[x] ? x : fa[x] = getfa(fa[x]); }
node mer(int mid, node l, node r) {
  node res;
  res.sum = l.sum + r.sum;
  for (int i = 1; i <= n; i++) {
    fa[l.l[i]] = l.l[i];
    fa[l.r[i]] = l.r[i];
    fa[r.l[i]] = r.l[i];
    fa[r.r[i]] = r.r[i];
  }
  for (int i = 1; i <= n; i++) {
    if (g[i][mid] == g[i][mid + 1]) {
      int xx = getfa(l.r[i]), yy = getfa(r.l[i]);
      if (xx == yy)
        continue;
      else
        fa[xx] = yy, res.sum--;
    }
  }
  for (int i = 1; i <= n; i++)
    res.l[i] = getfa(l.l[i]), res.r[i] = getfa(r.r[i]);
  return res;
}
void build(int o, int l, int r) {
  if (l == r) {
    tr[o].sum = n;
    for (int i = 1; i <= n; i++) {
      if (g[i][l] == g[i - 1][l])
        tr[o].l[i] = tr[o].r[i] = idx, tr[o].sum--;
      else
        tr[o].l[i] = tr[o].r[i] = ++idx;
    }
    return;
  }
  int mid = l + r >> 1;
  build((o << 1), l, mid);
  build((o << 1 | 1), mid + 1, r);
  tr[o] = mer(mid, tr[(o << 1)], tr[(o << 1 | 1)]);
}
node qry(int o, int l, int r, int ql, int qr) {
  if (ql <= l && r <= qr) return tr[o];
  int mid = l + r >> 1;
  if (qr <= mid)
    return qry((o << 1), l, mid, ql, qr);
  else if (mid < ql)
    return qry((o << 1 | 1), mid + 1, r, ql, qr);
  else
    return mer(mid, qry((o << 1), l, mid, ql, qr),
               qry((o << 1 | 1), mid + 1, r, ql, qr));
}
int main() {
  scanf("%d%d%d", &n, &m, &q);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) scanf("%d", &g[i][j]);
  build(1, 1, m);
  while (q--) {
    int x, y;
    scanf("%d%d", &x, &y);
    printf("%d\n", qry(1, 1, m, x, y).sum);
  }
  return 0;
}

```