#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const long long INFF = 0x3f3f3f3f3f3f3f3f;
const long long M = 1e9 + 7;
const long long maxn = 1e5 + 7;
const double eps = 0.00000001;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
template <typename T>
inline T abs(T a) {
  return a > 0 ? a : -a;
}
int n, m, q, l, r, i, j;
int a[11][maxn];
struct node {
  int lnum[11], rnum[11], ans, l, r;
} tree[maxn * 4];
int fa[44], to[44];
int getfather(int x) {
  if (fa[x] == x) return x;
  return fa[x] = getfather(fa[x]);
}
node merge(node x, node y) {
  node z;
  int i, num, cnt;
  for (i = 0; i < n * 4; i++) fa[i] = i, to[i] = -1;
  num = x.ans + y.ans;
  cnt = 0;
  for (i = 0; i < n; i++)
    if (a[i][x.r] == a[i][y.l]) {
      int fx = getfather(x.rnum[i]), fy = getfather(y.lnum[i] + n * 2);
      if (fx != fy) {
        fa[fx] = fy;
        num--;
      }
    }
  cnt = 0;
  for (i = 0; i < n; i++) {
    int f;
    f = getfather(x.lnum[i]);
    if (to[f] == -1) to[f] = cnt++;
    z.lnum[i] = to[f];
    f = getfather(y.rnum[i] + n * 2);
    if (to[f] == -1) to[f] = cnt++;
    z.rnum[i] = to[f];
  }
  z.ans = num;
  z.l = x.l;
  z.r = y.r;
  return z;
}
void build(int x, int l, int r) {
  tree[x].l = l;
  tree[x].r = r;
  if (l == r) {
    int i, t = 0;
    for (i = 0; i < n; i++) {
      tree[x].lnum[i] = tree[x].rnum[i] = t;
      if (a[i][l] != a[i + 1][l]) t++;
    }
    tree[x].ans = t;
    return;
  }
  int mid = (l + r) / 2;
  build(x << 1, l, mid);
  build(x << 1 | 1, mid + 1, r);
  tree[x] = merge(tree[x << 1], tree[x << 1 | 1]);
}
node query(int x, int l, int r, int L, int R) {
  if (l <= L && R <= r) return tree[x];
  int mid = (L + R) / 2;
  if (mid >= r) return query(x << 1, l, r, L, mid);
  if (l > mid) return query(x << 1 | 1, l, r, mid + 1, R);
  return merge(query(x << 1, l, r, L, mid),
               query(x << 1 | 1, l, r, mid + 1, R));
}
int main() {
  scanf("%d%d%d", &n, &m, &q);
  for (i = 0; i < n; i++)
    for (j = 1; j <= m; j++) scanf("%d", &a[i][j]);
  build(1, 1, m);
  while (q--) {
    scanf("%d%d", &l, &r);
    printf("%d\n", query(1, l, r, 1, m).ans);
  }
}

### Prompt

Develop a solution in Cpp to the problem described below:

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 INF = 0x3f3f3f3f;
const long long INFF = 0x3f3f3f3f3f3f3f3f;
const long long M = 1e9 + 7;
const long long maxn = 1e5 + 7;
const double eps = 0.00000001;
long long gcd(long long a, long long b) { return b ? gcd(b, a % b) : a; }
template <typename T>
inline T abs(T a) {
  return a > 0 ? a : -a;
}
int n, m, q, l, r, i, j;
int a[11][maxn];
struct node {
  int lnum[11], rnum[11], ans, l, r;
} tree[maxn * 4];
int fa[44], to[44];
int getfather(int x) {
  if (fa[x] == x) return x;
  return fa[x] = getfather(fa[x]);
}
node merge(node x, node y) {
  node z;
  int i, num, cnt;
  for (i = 0; i < n * 4; i++) fa[i] = i, to[i] = -1;
  num = x.ans + y.ans;
  cnt = 0;
  for (i = 0; i < n; i++)
    if (a[i][x.r] == a[i][y.l]) {
      int fx = getfather(x.rnum[i]), fy = getfather(y.lnum[i] + n * 2);
      if (fx != fy) {
        fa[fx] = fy;
        num--;
      }
    }
  cnt = 0;
  for (i = 0; i < n; i++) {
    int f;
    f = getfather(x.lnum[i]);
    if (to[f] == -1) to[f] = cnt++;
    z.lnum[i] = to[f];
    f = getfather(y.rnum[i] + n * 2);
    if (to[f] == -1) to[f] = cnt++;
    z.rnum[i] = to[f];
  }
  z.ans = num;
  z.l = x.l;
  z.r = y.r;
  return z;
}
void build(int x, int l, int r) {
  tree[x].l = l;
  tree[x].r = r;
  if (l == r) {
    int i, t = 0;
    for (i = 0; i < n; i++) {
      tree[x].lnum[i] = tree[x].rnum[i] = t;
      if (a[i][l] != a[i + 1][l]) t++;
    }
    tree[x].ans = t;
    return;
  }
  int mid = (l + r) / 2;
  build(x << 1, l, mid);
  build(x << 1 | 1, mid + 1, r);
  tree[x] = merge(tree[x << 1], tree[x << 1 | 1]);
}
node query(int x, int l, int r, int L, int R) {
  if (l <= L && R <= r) return tree[x];
  int mid = (L + R) / 2;
  if (mid >= r) return query(x << 1, l, r, L, mid);
  if (l > mid) return query(x << 1 | 1, l, r, mid + 1, R);
  return merge(query(x << 1, l, r, L, mid),
               query(x << 1 | 1, l, r, mid + 1, R));
}
int main() {
  scanf("%d%d%d", &n, &m, &q);
  for (i = 0; i < n; i++)
    for (j = 1; j <= m; j++) scanf("%d", &a[i][j]);
  build(1, 1, m);
  while (q--) {
    scanf("%d%d", &l, &r);
    printf("%d\n", query(1, l, r, 1, m).ans);
  }
}

```