#include <bits/stdc++.h>
using namespace std;
const int N = 10;
const int M = 100000 + 7;
int n;
int m;
int mt[N][M];
int jojo[4 * N + 7];
struct T {
  int sol;
  int l;
  int r;
  int first[N];
  int last[N];
};
T t[4 * M];
int par[4 * N + 7];
int id[4 * N + 7];
int root(int x) {
  if (par[x] == x) {
    return x;
  } else {
    return par[x] = root(par[x]);
  }
}
void unite(int x, int y) { par[root(x)] = root(y); }
T operator+(T a, T b) {
  if (a.sol == -1) {
    return b;
  }
  if (b.sol == -1) {
    return a;
  }
  int cnta = 0;
  int cntb = 0;
  for (int i = 0; i < n; i++) {
    cnta = max(cnta, max(a.first[i], a.last[i]));
    cntb = max(cntb, max(b.first[i], b.last[i]));
  }
  for (int i = 1; i <= cnta + cntb; i++) {
    par[i] = i;
  }
  int col = a.r;
  for (int i = 0; i < n; i++) {
    if (mt[i][col] == mt[i][col + 1]) {
      unite(a.last[i], b.first[i] + cnta);
    }
  }
  int cnt = 0;
  for (int i = 1; i <= cnta + cntb; i++) {
    if (par[i] == i) {
      cnt++;
      id[i] = cnt;
    }
    jojo[i] = 0;
  }
  int sol = a.sol + b.sol - cnta - cntb + cnt;
  int l = a.l;
  int r = b.r;
  int first[N];
  int last[N];
  for (int i = 0; i < n; i++) {
    first[i] = id[root(a.first[i])];
    last[i] = id[root(b.last[i] + cnta)];
    jojo[first[i]] = jojo[last[i]] = 1;
  }
  for (int i = 1; i <= cnta + cntb; i++) {
    jojo[i] += jojo[i - 1];
  }
  for (int i = 0; i < n; i++) {
    first[i] = jojo[first[i]];
    last[i] = jojo[last[i]];
  }
  a.sol = sol;
  a.l = l;
  a.r = r;
  for (int i = 0; i < n; i++) {
    a.first[i] = first[i];
    a.last[i] = last[i];
  }
  return a;
}
void build(int v, int tl, int tr) {
  if (tl == tr) {
    int sol = 0;
    for (int i = 0; i < n; i++) {
      if (i == 0 || mt[i][tl] != mt[i - 1][tl]) {
        sol++;
      }
      t[v].first[i] = t[v].last[i] = sol;
    }
    t[v].sol = sol;
    t[v].l = t[v].r = tl;
    return;
  }
  int tm = (tl + tr) / 2;
  build(2 * v, tl, tm);
  build(2 * v + 1, tm + 1, tr);
  t[v] = t[2 * v] + t[2 * v + 1];
}
T et;
T get(int v, int tl, int tr, int l, int r) {
  if (tr < l || r < tl) {
    return et;
  }
  if (l <= tl && tr <= r) {
    return t[v];
  }
  int tm = (tl + tr) / 2;
  return get(2 * v, tl, tm, l, r) + get(2 * v + 1, tm + 1, tr, l, r);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int q;
  et.sol = -1;
  cin >> n >> m >> q;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> mt[i][j];
    }
  }
  build(1, 0, m - 1);
  while (q--) {
    int l, r;
    cin >> l >> r;
    l--;
    r--;
    T it = get(1, 0, m - 1, l, r);
    cout << it.sol << "\n";
  }
  return 0;
}

### Prompt

Please provide a CPP coded solution 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 N = 10;
const int M = 100000 + 7;
int n;
int m;
int mt[N][M];
int jojo[4 * N + 7];
struct T {
  int sol;
  int l;
  int r;
  int first[N];
  int last[N];
};
T t[4 * M];
int par[4 * N + 7];
int id[4 * N + 7];
int root(int x) {
  if (par[x] == x) {
    return x;
  } else {
    return par[x] = root(par[x]);
  }
}
void unite(int x, int y) { par[root(x)] = root(y); }
T operator+(T a, T b) {
  if (a.sol == -1) {
    return b;
  }
  if (b.sol == -1) {
    return a;
  }
  int cnta = 0;
  int cntb = 0;
  for (int i = 0; i < n; i++) {
    cnta = max(cnta, max(a.first[i], a.last[i]));
    cntb = max(cntb, max(b.first[i], b.last[i]));
  }
  for (int i = 1; i <= cnta + cntb; i++) {
    par[i] = i;
  }
  int col = a.r;
  for (int i = 0; i < n; i++) {
    if (mt[i][col] == mt[i][col + 1]) {
      unite(a.last[i], b.first[i] + cnta);
    }
  }
  int cnt = 0;
  for (int i = 1; i <= cnta + cntb; i++) {
    if (par[i] == i) {
      cnt++;
      id[i] = cnt;
    }
    jojo[i] = 0;
  }
  int sol = a.sol + b.sol - cnta - cntb + cnt;
  int l = a.l;
  int r = b.r;
  int first[N];
  int last[N];
  for (int i = 0; i < n; i++) {
    first[i] = id[root(a.first[i])];
    last[i] = id[root(b.last[i] + cnta)];
    jojo[first[i]] = jojo[last[i]] = 1;
  }
  for (int i = 1; i <= cnta + cntb; i++) {
    jojo[i] += jojo[i - 1];
  }
  for (int i = 0; i < n; i++) {
    first[i] = jojo[first[i]];
    last[i] = jojo[last[i]];
  }
  a.sol = sol;
  a.l = l;
  a.r = r;
  for (int i = 0; i < n; i++) {
    a.first[i] = first[i];
    a.last[i] = last[i];
  }
  return a;
}
void build(int v, int tl, int tr) {
  if (tl == tr) {
    int sol = 0;
    for (int i = 0; i < n; i++) {
      if (i == 0 || mt[i][tl] != mt[i - 1][tl]) {
        sol++;
      }
      t[v].first[i] = t[v].last[i] = sol;
    }
    t[v].sol = sol;
    t[v].l = t[v].r = tl;
    return;
  }
  int tm = (tl + tr) / 2;
  build(2 * v, tl, tm);
  build(2 * v + 1, tm + 1, tr);
  t[v] = t[2 * v] + t[2 * v + 1];
}
T et;
T get(int v, int tl, int tr, int l, int r) {
  if (tr < l || r < tl) {
    return et;
  }
  if (l <= tl && tr <= r) {
    return t[v];
  }
  int tm = (tl + tr) / 2;
  return get(2 * v, tl, tm, l, r) + get(2 * v + 1, tm + 1, tr, l, r);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int q;
  et.sol = -1;
  cin >> n >> m >> q;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cin >> mt[i][j];
    }
  }
  build(1, 0, m - 1);
  while (q--) {
    int l, r;
    cin >> l >> r;
    l--;
    r--;
    T it = get(1, 0, m - 1, l, r);
    cout << it.sol << "\n";
  }
  return 0;
}

```