#include <bits/stdc++.h>
int inp() {
  char c = getchar();
  while (c < '0' || c > '9') c = getchar();
  int sum = 0;
  while (c >= '0' && c <= '9') {
    sum = sum * 10 + c - '0';
    c = getchar();
  }
  return sum;
}
int n, m;
int num[12][100010];
struct SEG {
  int l;
  int r;
  int ls[12];
  int rs[12];
  int sum;
  int cnt;
} nul;
int fa[42];
int used[42];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
SEG operator+(SEG a, SEG b) {
  if (a.l == -1) return b;
  if (b.l == -1) return a;
  SEG ret;
  ret.l = a.l;
  ret.r = b.r;
  ret.sum = a.sum + b.sum;
  for (int i = 1; i <= a.cnt + b.cnt; i++) fa[i] = i;
  memset(used, 0, sizeof(used));
  for (int i = 1; i <= n; i++) {
    b.ls[i] += a.cnt;
    b.rs[i] += a.cnt;
  }
  for (int i = 1; i <= n; i++) {
    if (num[i][a.r] == num[i][b.l]) {
      int f1 = find(a.rs[i]);
      int f2 = find(b.ls[i]);
      if (f1 != f2) {
        ret.sum--;
        fa[f1] = f2;
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    ret.ls[i] = find(a.ls[i]);
    ret.rs[i] = find(b.rs[i]);
  }
  int cnt = 0;
  for (int i = 1; i <= n; i++) {
    if (!used[ret.ls[i]]) used[ret.ls[i]] = ++cnt;
    ret.ls[i] = used[ret.ls[i]];
    if (!used[ret.rs[i]]) used[ret.rs[i]] = ++cnt;
    ret.rs[i] = used[ret.rs[i]];
  }
  ret.cnt = cnt;
  return ret;
}
struct SEG_Tree {
  SEG t[400010];
  void push_up(int cur) { t[cur] = t[((cur) << 1)] + t[((cur) << 1 | 1)]; }
  void build(int cur, int l, int r) {
    t[cur].l = l;
    t[cur].r = r;
    if (l == r) {
      int cnt = 0;
      for (int i = 1; i <= n; i++) {
        if (num[i][l] != num[i - 1][l]) {
          t[cur].sum++;
          t[cur].ls[i] = t[cur].rs[i] = ++cnt;
        } else
          t[cur].ls[i] = t[cur].rs[i] = t[cur].ls[i - 1];
      }
      t[cur].cnt = cnt;
      return;
    }
    int mid = (l + r) >> 1;
    build(((cur) << 1), l, mid);
    build(((cur) << 1 | 1), mid + 1, r);
    push_up(cur);
  }
  SEG query(int cur, int l, int r) {
    if (t[cur].l > r || t[cur].r < l) return nul;
    if (t[cur].l >= l && t[cur].r <= r) return t[cur];
    return query(((cur) << 1), l, r) + query(((cur) << 1 | 1), l, r);
  }
} t;
int main() {
  nul.l = -1;
  n = inp();
  m = inp();
  int q = inp();
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) num[i][j] = inp();
  t.build(1, 1, m);
  while (q--) {
    int l = inp();
    int r = inp();
    printf("%d\n", t.query(1, l, r).sum);
  }
}

### 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>
int inp() {
  char c = getchar();
  while (c < '0' || c > '9') c = getchar();
  int sum = 0;
  while (c >= '0' && c <= '9') {
    sum = sum * 10 + c - '0';
    c = getchar();
  }
  return sum;
}
int n, m;
int num[12][100010];
struct SEG {
  int l;
  int r;
  int ls[12];
  int rs[12];
  int sum;
  int cnt;
} nul;
int fa[42];
int used[42];
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
SEG operator+(SEG a, SEG b) {
  if (a.l == -1) return b;
  if (b.l == -1) return a;
  SEG ret;
  ret.l = a.l;
  ret.r = b.r;
  ret.sum = a.sum + b.sum;
  for (int i = 1; i <= a.cnt + b.cnt; i++) fa[i] = i;
  memset(used, 0, sizeof(used));
  for (int i = 1; i <= n; i++) {
    b.ls[i] += a.cnt;
    b.rs[i] += a.cnt;
  }
  for (int i = 1; i <= n; i++) {
    if (num[i][a.r] == num[i][b.l]) {
      int f1 = find(a.rs[i]);
      int f2 = find(b.ls[i]);
      if (f1 != f2) {
        ret.sum--;
        fa[f1] = f2;
      }
    }
  }
  for (int i = 1; i <= n; i++) {
    ret.ls[i] = find(a.ls[i]);
    ret.rs[i] = find(b.rs[i]);
  }
  int cnt = 0;
  for (int i = 1; i <= n; i++) {
    if (!used[ret.ls[i]]) used[ret.ls[i]] = ++cnt;
    ret.ls[i] = used[ret.ls[i]];
    if (!used[ret.rs[i]]) used[ret.rs[i]] = ++cnt;
    ret.rs[i] = used[ret.rs[i]];
  }
  ret.cnt = cnt;
  return ret;
}
struct SEG_Tree {
  SEG t[400010];
  void push_up(int cur) { t[cur] = t[((cur) << 1)] + t[((cur) << 1 | 1)]; }
  void build(int cur, int l, int r) {
    t[cur].l = l;
    t[cur].r = r;
    if (l == r) {
      int cnt = 0;
      for (int i = 1; i <= n; i++) {
        if (num[i][l] != num[i - 1][l]) {
          t[cur].sum++;
          t[cur].ls[i] = t[cur].rs[i] = ++cnt;
        } else
          t[cur].ls[i] = t[cur].rs[i] = t[cur].ls[i - 1];
      }
      t[cur].cnt = cnt;
      return;
    }
    int mid = (l + r) >> 1;
    build(((cur) << 1), l, mid);
    build(((cur) << 1 | 1), mid + 1, r);
    push_up(cur);
  }
  SEG query(int cur, int l, int r) {
    if (t[cur].l > r || t[cur].r < l) return nul;
    if (t[cur].l >= l && t[cur].r <= r) return t[cur];
    return query(((cur) << 1), l, r) + query(((cur) << 1 | 1), l, r);
  }
} t;
int main() {
  nul.l = -1;
  n = inp();
  m = inp();
  int q = inp();
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) num[i][j] = inp();
  t.build(1, 1, m);
  while (q--) {
    int l = inp();
    int r = inp();
    printf("%d\n", t.query(1, l, r).sum);
  }
}

```