#include <bits/stdc++.h>
const int MAXINT = 2147483640;
const long long MAXLL = 9223372036854775800LL;
const long long MAXN = 1000000;
using namespace std;
struct Tree {
  int val, l[11], r[11];
};
Tree t[MAXN];
int a[15][100005];
int p[MAXN];
int n, m, now = 0;
int Get(int v) {
  if (p[v] != v) p[v] = Get(p[v]);
  return p[v];
}
Tree merge_(Tree x, Tree y, int c) {
  Tree ans;
  ans.val = x.val + y.val;
  for (int i = 1; i <= n; ++i)
    p[x.l[i]] = x.l[i], p[x.r[i]] = x.r[i], p[y.l[i]] = y.l[i],
    p[y.r[i]] = y.r[i];
  for (int i = 1; i <= n; ++i) {
    if (a[i][c] == a[i][c + 1] && Get(x.r[i]) != Get(y.l[i])) {
      --ans.val;
      p[Get(x.r[i])] = Get(y.l[i]);
    }
  }
  for (int i = 1; i <= n; ++i) ans.l[i] = Get(x.l[i]), ans.r[i] = Get(y.r[i]);
  return ans;
}
void build(int v, int tl, int tr) {
  if (tl == tr) {
    for (int i = 1; i <= n; ++i) {
      if (a[i][tl] != a[i - 1][tl])
        t[v].l[i] = t[v].r[i] = ++now, t[v].val++;
      else
        t[v].l[i] = t[v].r[i] = t[v].l[i - 1];
    }
  } else {
    int tm = (tl + tr) / 2;
    build(v * 2, tl, tm);
    build(v * 2 + 1, tm + 1, tr);
    t[v] = merge_(t[v * 2], t[v * 2 + 1], tm);
  }
}
Tree get(int v, int tl, int tr, int l, int r) {
  if (tl == l && tr == r) return t[v];
  int tm = (tl + tr) / 2;
  if (r <= tm)
    return get(v * 2, tl, tm, l, r);
  else if (l > tm)
    return get(v * 2 + 1, tm + 1, tr, l, r);
  else
    return merge_(get(v * 2, tl, tm, l, tm),
                  get(v * 2 + 1, tm + 1, tr, tm + 1, r), tm);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int q, i, j;
  cin >> n >> m >> q;
  for (i = 1; i <= n; ++i) {
    for (j = 1; j <= m; ++j) cin >> a[i][j];
  }
  build(1, 1, m);
  for (i = 1; i <= q; ++i) {
    int l, r;
    cin >> l >> r;
    cout << get(1, 1, m, l, r).val << endl;
  }
  return 0;
}

### Prompt

Create a solution in cpp for 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 MAXINT = 2147483640;
const long long MAXLL = 9223372036854775800LL;
const long long MAXN = 1000000;
using namespace std;
struct Tree {
  int val, l[11], r[11];
};
Tree t[MAXN];
int a[15][100005];
int p[MAXN];
int n, m, now = 0;
int Get(int v) {
  if (p[v] != v) p[v] = Get(p[v]);
  return p[v];
}
Tree merge_(Tree x, Tree y, int c) {
  Tree ans;
  ans.val = x.val + y.val;
  for (int i = 1; i <= n; ++i)
    p[x.l[i]] = x.l[i], p[x.r[i]] = x.r[i], p[y.l[i]] = y.l[i],
    p[y.r[i]] = y.r[i];
  for (int i = 1; i <= n; ++i) {
    if (a[i][c] == a[i][c + 1] && Get(x.r[i]) != Get(y.l[i])) {
      --ans.val;
      p[Get(x.r[i])] = Get(y.l[i]);
    }
  }
  for (int i = 1; i <= n; ++i) ans.l[i] = Get(x.l[i]), ans.r[i] = Get(y.r[i]);
  return ans;
}
void build(int v, int tl, int tr) {
  if (tl == tr) {
    for (int i = 1; i <= n; ++i) {
      if (a[i][tl] != a[i - 1][tl])
        t[v].l[i] = t[v].r[i] = ++now, t[v].val++;
      else
        t[v].l[i] = t[v].r[i] = t[v].l[i - 1];
    }
  } else {
    int tm = (tl + tr) / 2;
    build(v * 2, tl, tm);
    build(v * 2 + 1, tm + 1, tr);
    t[v] = merge_(t[v * 2], t[v * 2 + 1], tm);
  }
}
Tree get(int v, int tl, int tr, int l, int r) {
  if (tl == l && tr == r) return t[v];
  int tm = (tl + tr) / 2;
  if (r <= tm)
    return get(v * 2, tl, tm, l, r);
  else if (l > tm)
    return get(v * 2 + 1, tm + 1, tr, l, r);
  else
    return merge_(get(v * 2, tl, tm, l, tm),
                  get(v * 2 + 1, tm + 1, tr, tm + 1, r), tm);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int q, i, j;
  cin >> n >> m >> q;
  for (i = 1; i <= n; ++i) {
    for (j = 1; j <= m; ++j) cin >> a[i][j];
  }
  build(1, 1, m);
  for (i = 1; i <= q; ++i) {
    int l, r;
    cin >> l >> r;
    cout << get(1, 1, m, l, r).val << endl;
  }
  return 0;
}

```