#include <bits/stdc++.h>
using namespace std;
struct node {
  int u[11], d[11], ans, l, r;
} t[101010 * 4];
int a[101010][11], f[42], n, m, q, x, v[42], y;
int get(int x) { return x == f[x] ? x : f[x] = get(f[x]); }
node merge(node x, node y) {
  node tmp;
  tmp.l = x.l;
  tmp.r = y.r;
  tmp.ans = x.ans + y.ans;
  for (int i = 1; i <= n; i++) {
    f[i] = x.u[i];
    f[i + n] = x.d[i];
    f[i + n * 2] = y.u[i] + 2 * n;
    f[i + n * 3] = y.d[i] + 2 * n;
  }
  for (int i = 1; i <= n; i++)
    if (a[x.r][i] == a[x.r + 1][i]) {
      int p = get(i + n), q = get(i + n * 2);
      if (p != q) f[q] = p, tmp.ans--;
    }
  memset(v, 0, sizeof(v));
  for (int i = 1; i <= n; i++) {
    tmp.u[i] = get(i);
    if (!v[tmp.u[i]]) v[tmp.u[i]] = i;
    tmp.u[i] = v[tmp.u[i]];
    tmp.d[i] = get(i + 3 * n);
    if (!v[tmp.d[i]]) v[tmp.d[i]] = i + n;
    tmp.d[i] = v[tmp.d[i]];
  }
  return tmp;
}
void build(int k, int l, int r) {
  t[k].l = l, t[k].r = r;
  if (l == r) {
    t[k].u[1] = t[k].d[1] = t[k].ans = 1;
    for (int i = 2; i <= n; i++)
      if (a[l][i] == a[l][i - 1])
        t[k].u[i] = t[k].d[i] = t[k].u[i - 1];
      else
        t[k].u[i] = t[k].d[i] = i, t[k].ans++;
    return;
  }
  int m = (l + r) / 2;
  build(k * 2, l, m);
  build(k * 2 + 1, m + 1, r);
  t[k] = merge(t[k * 2], t[k * 2 + 1]);
}
node solve(int k, int x, int y) {
  int l = t[k].l, r = t[k].r;
  if (l == x && r == y) return t[k];
  int m = (l + r) / 2;
  if (y <= m) return solve(k * 2, x, y);
  if (x > m) return solve(k * 2 + 1, x, y);
  return merge(solve(k * 2, x, m), solve(k * 2 + 1, m + 1, y));
}
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", &a[j][i]);
  build(1, 1, m);
  for (int i = 1; i <= q; i++) {
    scanf("%d%d", &x, &y);
    printf("%d\n", solve(1, x, y).ans);
  }
}

### Prompt

Your task is to create 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;
struct node {
  int u[11], d[11], ans, l, r;
} t[101010 * 4];
int a[101010][11], f[42], n, m, q, x, v[42], y;
int get(int x) { return x == f[x] ? x : f[x] = get(f[x]); }
node merge(node x, node y) {
  node tmp;
  tmp.l = x.l;
  tmp.r = y.r;
  tmp.ans = x.ans + y.ans;
  for (int i = 1; i <= n; i++) {
    f[i] = x.u[i];
    f[i + n] = x.d[i];
    f[i + n * 2] = y.u[i] + 2 * n;
    f[i + n * 3] = y.d[i] + 2 * n;
  }
  for (int i = 1; i <= n; i++)
    if (a[x.r][i] == a[x.r + 1][i]) {
      int p = get(i + n), q = get(i + n * 2);
      if (p != q) f[q] = p, tmp.ans--;
    }
  memset(v, 0, sizeof(v));
  for (int i = 1; i <= n; i++) {
    tmp.u[i] = get(i);
    if (!v[tmp.u[i]]) v[tmp.u[i]] = i;
    tmp.u[i] = v[tmp.u[i]];
    tmp.d[i] = get(i + 3 * n);
    if (!v[tmp.d[i]]) v[tmp.d[i]] = i + n;
    tmp.d[i] = v[tmp.d[i]];
  }
  return tmp;
}
void build(int k, int l, int r) {
  t[k].l = l, t[k].r = r;
  if (l == r) {
    t[k].u[1] = t[k].d[1] = t[k].ans = 1;
    for (int i = 2; i <= n; i++)
      if (a[l][i] == a[l][i - 1])
        t[k].u[i] = t[k].d[i] = t[k].u[i - 1];
      else
        t[k].u[i] = t[k].d[i] = i, t[k].ans++;
    return;
  }
  int m = (l + r) / 2;
  build(k * 2, l, m);
  build(k * 2 + 1, m + 1, r);
  t[k] = merge(t[k * 2], t[k * 2 + 1]);
}
node solve(int k, int x, int y) {
  int l = t[k].l, r = t[k].r;
  if (l == x && r == y) return t[k];
  int m = (l + r) / 2;
  if (y <= m) return solve(k * 2, x, y);
  if (x > m) return solve(k * 2 + 1, x, y);
  return merge(solve(k * 2, x, m), solve(k * 2 + 1, m + 1, y));
}
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", &a[j][i]);
  build(1, 1, m);
  for (int i = 1; i <= q; i++) {
    scanf("%d%d", &x, &y);
    printf("%d\n", solve(1, x, y).ans);
  }
}

```