#include <bits/stdc++.h>
const int MAXN = 1e5 + 7;
struct Node {
  int x, y;
  int sum;
  int l[11], r[11];
};
Node tree[MAXN * 3];
int q;
int n, m;
int mp[11][MAXN];
int fafa[MAXN * 11], tot = 0;
int find(int a) {
  if (fafa[a] != a) fafa[a] = find(fafa[a]);
  return fafa[a];
}
Node update(const int &ll, const int &rr, const Node lc, const Node rc,
            const int &mid) {
  Node ans;
  ans.x = ll;
  ans.y = rr;
  ans.sum = lc.sum + rc.sum;
  for (register int i = 1; i <= n; ++i) {
    fafa[lc.l[i]] = lc.l[i];
    fafa[lc.r[i]] = lc.r[i];
    fafa[rc.l[i]] = rc.l[i];
    fafa[rc.r[i]] = rc.r[i];
  }
  for (register int i = 1; i <= n; ++i) {
    if (mp[i][mid] == mp[i][mid + 1]) {
      int f1 = find(lc.r[i]);
      int f2 = find(rc.l[i]);
      (f1 != f2) && (fafa[f1] = f2, ans.sum--);
    }
  }
  for (register int i = 1; i <= n; ++i) {
    ans.l[i] = find(lc.l[i]);
    ans.r[i] = find(rc.r[i]);
  }
  return ans;
}
void build(const int &bh, const int &ll, const int &rr) {
  tree[bh].x = ll;
  tree[bh].y = rr;
  if (ll == rr) {
    tree[bh].sum = n;
    for (register int i = 1; i <= n; ++i) {
      if (mp[i][ll] == mp[i - 1][ll]) {
        tree[bh].l[i] = tree[bh].r[i] = tree[bh].l[i - 1];
        tree[bh].sum--;
      } else {
        tree[bh].l[i] = tree[bh].r[i] = ++tot;
      }
    }
    return;
  }
  register const int mid = (ll + rr) >> 1;
  build(bh << 1, ll, mid);
  build(bh << 1 | 1, mid + 1, rr);
  tree[bh] =
      update(tree[bh].x, tree[bh].y, tree[bh << 1], tree[bh << 1 | 1], mid);
}
Node ask(const int &bh, const int &ll, const int &rr) {
  if (tree[bh].x >= ll && tree[bh].y <= rr) return tree[bh];
  register const int mid = (tree[bh].x + tree[bh].y) >> 1;
  if (rr <= mid)
    return ask(bh << 1, ll, rr);
  else if (ll > mid)
    return ask(bh << 1 | 1, ll, rr);
  else
    return update(ll, rr, ask(bh << 1, ll, rr), ask(bh << 1 | 1, ll, rr), mid);
}
inline int SlowRead() {
  char ch = 0;
  int data = 0, f = 1;
  while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
  if (ch == '-') f = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') {
    data = data * 10 + ch - '0';
    ch = getchar();
  }
  return data * f;
}
int main(int argc, char const *argv[]) {
  n = SlowRead();
  m = SlowRead();
  q = SlowRead();
  for (register int i = 1; i <= n; ++i)
    for (register int j = 1; j <= m; j++) mp[i][j] = SlowRead();
  tot = 0;
  build(1, 1, m);
  int u, w;
  while (q-- > 0) {
    u = SlowRead();
    w = SlowRead();
    Node ans = ask(1, u, w);
    printf("%d\n", ans.sum);
  }
  return 0;
}

### 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>
const int MAXN = 1e5 + 7;
struct Node {
  int x, y;
  int sum;
  int l[11], r[11];
};
Node tree[MAXN * 3];
int q;
int n, m;
int mp[11][MAXN];
int fafa[MAXN * 11], tot = 0;
int find(int a) {
  if (fafa[a] != a) fafa[a] = find(fafa[a]);
  return fafa[a];
}
Node update(const int &ll, const int &rr, const Node lc, const Node rc,
            const int &mid) {
  Node ans;
  ans.x = ll;
  ans.y = rr;
  ans.sum = lc.sum + rc.sum;
  for (register int i = 1; i <= n; ++i) {
    fafa[lc.l[i]] = lc.l[i];
    fafa[lc.r[i]] = lc.r[i];
    fafa[rc.l[i]] = rc.l[i];
    fafa[rc.r[i]] = rc.r[i];
  }
  for (register int i = 1; i <= n; ++i) {
    if (mp[i][mid] == mp[i][mid + 1]) {
      int f1 = find(lc.r[i]);
      int f2 = find(rc.l[i]);
      (f1 != f2) && (fafa[f1] = f2, ans.sum--);
    }
  }
  for (register int i = 1; i <= n; ++i) {
    ans.l[i] = find(lc.l[i]);
    ans.r[i] = find(rc.r[i]);
  }
  return ans;
}
void build(const int &bh, const int &ll, const int &rr) {
  tree[bh].x = ll;
  tree[bh].y = rr;
  if (ll == rr) {
    tree[bh].sum = n;
    for (register int i = 1; i <= n; ++i) {
      if (mp[i][ll] == mp[i - 1][ll]) {
        tree[bh].l[i] = tree[bh].r[i] = tree[bh].l[i - 1];
        tree[bh].sum--;
      } else {
        tree[bh].l[i] = tree[bh].r[i] = ++tot;
      }
    }
    return;
  }
  register const int mid = (ll + rr) >> 1;
  build(bh << 1, ll, mid);
  build(bh << 1 | 1, mid + 1, rr);
  tree[bh] =
      update(tree[bh].x, tree[bh].y, tree[bh << 1], tree[bh << 1 | 1], mid);
}
Node ask(const int &bh, const int &ll, const int &rr) {
  if (tree[bh].x >= ll && tree[bh].y <= rr) return tree[bh];
  register const int mid = (tree[bh].x + tree[bh].y) >> 1;
  if (rr <= mid)
    return ask(bh << 1, ll, rr);
  else if (ll > mid)
    return ask(bh << 1 | 1, ll, rr);
  else
    return update(ll, rr, ask(bh << 1, ll, rr), ask(bh << 1 | 1, ll, rr), mid);
}
inline int SlowRead() {
  char ch = 0;
  int data = 0, f = 1;
  while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
  if (ch == '-') f = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') {
    data = data * 10 + ch - '0';
    ch = getchar();
  }
  return data * f;
}
int main(int argc, char const *argv[]) {
  n = SlowRead();
  m = SlowRead();
  q = SlowRead();
  for (register int i = 1; i <= n; ++i)
    for (register int j = 1; j <= m; j++) mp[i][j] = SlowRead();
  tot = 0;
  build(1, 1, m);
  int u, w;
  while (q-- > 0) {
    u = SlowRead();
    w = SlowRead();
    Node ans = ask(1, u, w);
    printf("%d\n", ans.sum);
  }
  return 0;
}

```