#include <bits/stdc++.h>
using namespace std;
const int maxn = 100010;
int n, f[maxn << 4], cnt;
int grid[10][maxn];
struct Node {
  int Lh[10], Rh[10];
  int sum;
};
Node mem[maxn << 2];
int Find_root(int u) {
  if (f[u] == u)
    return u;
  else
    return f[u] = Find_root(f[u]);
}
Node update(Node L, Node R, int md) {
  Node res;
  res.sum = L.sum + R.sum;
  for (int i = 0; i < n; i++) {
    f[L.Lh[i]] = L.Lh[i];
    f[L.Rh[i]] = L.Rh[i];
    f[R.Lh[i]] = R.Lh[i];
    f[R.Rh[i]] = R.Rh[i];
  }
  for (int i = 0; i < n; i++)
    if (grid[i][md] == grid[i][md + 1]) {
      int dx = Find_root(L.Rh[i]), dy = Find_root(R.Lh[i]);
      if (dx != dy) {
        f[dx] = dy;
        res.sum--;
      }
    }
  for (int i = 0; i < n; i++) {
    res.Lh[i] = Find_root(L.Lh[i]);
    res.Rh[i] = Find_root(R.Rh[i]);
  }
  return res;
}
void build(int u, int L, int R) {
  if (L == R) {
    mem[u].sum = 1;
    mem[u].Lh[0] = mem[u].Rh[0] = cnt++;
    for (int i = 1; i < n; i++) {
      if (grid[i][L] != grid[i - 1][L]) {
        mem[u].Lh[i] = mem[u].Rh[i] = cnt++;
        mem[u].sum++;
      } else
        mem[u].Lh[i] = mem[u].Rh[i] = mem[u].Lh[i - 1];
    }
    return;
  }
  int md = L + R >> 1, ls = u << 1, rs = ls | 1;
  build(ls, L, md);
  build(rs, md + 1, R);
  mem[u] = update(mem[ls], mem[rs], md);
}
Node calc(int u, int L, int R, int l, int r) {
  if (l <= L and R <= r) return mem[u];
  int md = L + R >> 1, ls = u << 1, rs = ls | 1;
  if (r <= md)
    return calc(ls, L, md, l, r);
  else if (md < l)
    return calc(rs, md + 1, R, l, r);
  else
    return update(calc(ls, L, md, l, r), calc(rs, md + 1, R, l, r), md);
}
int m, q, l, r;
int main() {
  scanf("%d%d%d", &n, &m, &q);
  for (int i = 0; i < n; i++) {
    for (int j = 1; j <= m; j++) scanf("%d", &grid[i][j]);
  }
  build(1, 1, m);
  while (q--) {
    scanf("%d%d", &l, &r);
    printf("%d\n", calc(1, 1, m, l, r).sum);
  }
  return 0;
}

### 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;
const int maxn = 100010;
int n, f[maxn << 4], cnt;
int grid[10][maxn];
struct Node {
  int Lh[10], Rh[10];
  int sum;
};
Node mem[maxn << 2];
int Find_root(int u) {
  if (f[u] == u)
    return u;
  else
    return f[u] = Find_root(f[u]);
}
Node update(Node L, Node R, int md) {
  Node res;
  res.sum = L.sum + R.sum;
  for (int i = 0; i < n; i++) {
    f[L.Lh[i]] = L.Lh[i];
    f[L.Rh[i]] = L.Rh[i];
    f[R.Lh[i]] = R.Lh[i];
    f[R.Rh[i]] = R.Rh[i];
  }
  for (int i = 0; i < n; i++)
    if (grid[i][md] == grid[i][md + 1]) {
      int dx = Find_root(L.Rh[i]), dy = Find_root(R.Lh[i]);
      if (dx != dy) {
        f[dx] = dy;
        res.sum--;
      }
    }
  for (int i = 0; i < n; i++) {
    res.Lh[i] = Find_root(L.Lh[i]);
    res.Rh[i] = Find_root(R.Rh[i]);
  }
  return res;
}
void build(int u, int L, int R) {
  if (L == R) {
    mem[u].sum = 1;
    mem[u].Lh[0] = mem[u].Rh[0] = cnt++;
    for (int i = 1; i < n; i++) {
      if (grid[i][L] != grid[i - 1][L]) {
        mem[u].Lh[i] = mem[u].Rh[i] = cnt++;
        mem[u].sum++;
      } else
        mem[u].Lh[i] = mem[u].Rh[i] = mem[u].Lh[i - 1];
    }
    return;
  }
  int md = L + R >> 1, ls = u << 1, rs = ls | 1;
  build(ls, L, md);
  build(rs, md + 1, R);
  mem[u] = update(mem[ls], mem[rs], md);
}
Node calc(int u, int L, int R, int l, int r) {
  if (l <= L and R <= r) return mem[u];
  int md = L + R >> 1, ls = u << 1, rs = ls | 1;
  if (r <= md)
    return calc(ls, L, md, l, r);
  else if (md < l)
    return calc(rs, md + 1, R, l, r);
  else
    return update(calc(ls, L, md, l, r), calc(rs, md + 1, R, l, r), md);
}
int m, q, l, r;
int main() {
  scanf("%d%d%d", &n, &m, &q);
  for (int i = 0; i < n; i++) {
    for (int j = 1; j <= m; j++) scanf("%d", &grid[i][j]);
  }
  build(1, 1, m);
  while (q--) {
    scanf("%d%d", &l, &r);
    printf("%d\n", calc(1, 1, m, l, r).sum);
  }
  return 0;
}

```