#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const long long inf = 1e9;
const long long mod = 1e9 + 7;
const int maxn = 1e5 + 10;
const int maxm = 10;
struct node {
  int left[maxm], right[maxm], cnt;
} f[maxn << 2];
int n, m, id;
int a[maxn][10], fa[maxn * 10], tl[maxm], tr[maxm];
int getf(int d) {
  if (fa[d] == d) return d;
  fa[d] = getf(fa[d]);
  return fa[d];
}
void merge_interval(node &x, node &y, node &z, int pos) {
  int i, cnt = 0;
  memcpy(tl, y.right, n * 4);
  memcpy(tr, z.left, n * 4);
  for (i = 0; i < n; i++) {
    fa[tl[i]] = tl[i];
    fa[tr[i]] = tr[i];
    fa[y.left[i]] = y.left[i];
    fa[z.right[i]] = z.right[i];
  }
  for (i = 0; i < n; i++)
    if (a[pos][i] == a[pos + 1][i]) {
      tl[i] = getf(tl[i]);
      tr[i] = getf(tr[i]);
      if (tl[i] != tr[i]) {
        fa[tl[i]] = tr[i];
        cnt++;
      }
    }
  x.cnt = y.cnt + z.cnt - cnt;
  for (i = 0; i < n; i++) {
    x.left[i] = getf(y.left[i]);
    x.right[i] = getf(z.right[i]);
  }
}
void build(int ind, int l, int r) {
  if (l == r) {
    int cnt = 0, i;
    for (i = 0; i < n; i++) {
      if (i == 0 || a[l][i] != a[l][i - 1]) id++, cnt++;
      f[ind].left[i] = f[ind].right[i] = id;
    }
    f[ind].cnt = cnt;
    return;
  }
  int m = (l + r) >> 1;
  build(ind << 1, l, m);
  build(ind << 1 | 1, m + 1, r);
  merge_interval(f[ind], f[ind << 1], f[ind << 1 | 1], m);
}
node query(int ind, int l, int r, int x, int y) {
  if (x <= l && r <= y) return f[ind];
  int m = (l + r) >> 1;
  node u, v, w;
  if (x <= m) u = query(ind << 1, l, m, x, y);
  if (m < y) v = query(ind << 1 | 1, m + 1, r, x, y);
  if (x <= m && m < y) {
    merge_interval(w, u, v, m);
    return w;
  } else if (x <= m)
    return u;
  else
    return v;
}
int main() {
  int Q, i, j;
  scanf("%d%d%d", &n, &m, &Q);
  for (i = 0; i < n; i++)
    for (j = 0; j < m; j++) scanf("%d", &a[j][i]);
  build(1, 0, m - 1);
  while (Q--) {
    scanf("%d%d", &i, &j);
    i--, j--;
    printf("%d\n", query(1, 0, m - 1, i, j).cnt);
  }
  return 0;
}

### Prompt

In CPP, your task is to solve 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 double eps = 1e-8;
const long long inf = 1e9;
const long long mod = 1e9 + 7;
const int maxn = 1e5 + 10;
const int maxm = 10;
struct node {
  int left[maxm], right[maxm], cnt;
} f[maxn << 2];
int n, m, id;
int a[maxn][10], fa[maxn * 10], tl[maxm], tr[maxm];
int getf(int d) {
  if (fa[d] == d) return d;
  fa[d] = getf(fa[d]);
  return fa[d];
}
void merge_interval(node &x, node &y, node &z, int pos) {
  int i, cnt = 0;
  memcpy(tl, y.right, n * 4);
  memcpy(tr, z.left, n * 4);
  for (i = 0; i < n; i++) {
    fa[tl[i]] = tl[i];
    fa[tr[i]] = tr[i];
    fa[y.left[i]] = y.left[i];
    fa[z.right[i]] = z.right[i];
  }
  for (i = 0; i < n; i++)
    if (a[pos][i] == a[pos + 1][i]) {
      tl[i] = getf(tl[i]);
      tr[i] = getf(tr[i]);
      if (tl[i] != tr[i]) {
        fa[tl[i]] = tr[i];
        cnt++;
      }
    }
  x.cnt = y.cnt + z.cnt - cnt;
  for (i = 0; i < n; i++) {
    x.left[i] = getf(y.left[i]);
    x.right[i] = getf(z.right[i]);
  }
}
void build(int ind, int l, int r) {
  if (l == r) {
    int cnt = 0, i;
    for (i = 0; i < n; i++) {
      if (i == 0 || a[l][i] != a[l][i - 1]) id++, cnt++;
      f[ind].left[i] = f[ind].right[i] = id;
    }
    f[ind].cnt = cnt;
    return;
  }
  int m = (l + r) >> 1;
  build(ind << 1, l, m);
  build(ind << 1 | 1, m + 1, r);
  merge_interval(f[ind], f[ind << 1], f[ind << 1 | 1], m);
}
node query(int ind, int l, int r, int x, int y) {
  if (x <= l && r <= y) return f[ind];
  int m = (l + r) >> 1;
  node u, v, w;
  if (x <= m) u = query(ind << 1, l, m, x, y);
  if (m < y) v = query(ind << 1 | 1, m + 1, r, x, y);
  if (x <= m && m < y) {
    merge_interval(w, u, v, m);
    return w;
  } else if (x <= m)
    return u;
  else
    return v;
}
int main() {
  int Q, i, j;
  scanf("%d%d%d", &n, &m, &Q);
  for (i = 0; i < n; i++)
    for (j = 0; j < m; j++) scanf("%d", &a[j][i]);
  build(1, 0, m - 1);
  while (Q--) {
    scanf("%d%d", &i, &j);
    i--, j--;
    printf("%d\n", query(1, 0, m - 1, i, j).cnt);
  }
  return 0;
}

```