#include <bits/stdc++.h>
using namespace std;
const int kInf = (1 << 20);
const int kSq = 330;
const int kMaxN = 1e5 + 10;
int n, m, Q;
int v[kMaxN][12];
struct Query {
  int l, r, i;
  bool operator<(const Query& other) const { return r < other.r; }
} q[kMaxN];
int ans[kMaxN];
int t[11 * kMaxN], d[11 * kMaxN];
int merges;
int parent(int a) {
  if (t[a]) {
    return t[a] = parent(t[a]);
  }
  return a;
}
void unite(int a, int b) {
  a = parent(a);
  b = parent(b);
  if (a == b) return;
  ++merges;
  if (d[a] < d[b]) {
    t[a] = b;
  } else {
    t[b] = a;
    if (d[a] == d[b]) {
      ++d[a];
    }
  }
}
struct Segment {
  int l, r;
  vector<int> l_side, r_side;
  int cnt;
  Segment() {
    l_side.resize(n + 1);
    r_side.resize(n + 1);
  }
  Segment(int j) : l(j), r(j) {
    l_side.resize(n + 1);
    r_side.resize(n + 1);
    cnt = 0;
    for (int i = 1; i <= n; ++i) {
      if (i != 1 && v[l][i] == v[l][i - 1]) {
        l_side[i] = l_side[i - 1];
        r_side[i] = r_side[i - 1];
      } else {
        ++cnt;
        l_side[i] = (j - 1) * n + i;
        r_side[i] = (j - 1) * n + i;
      }
    }
  }
};
Segment Compose(const Segment& a, const Segment& b) {
  Segment res;
  res.l = a.l;
  res.r = b.r;
  for (int i = 1; i <= n; ++i) {
    t[a.l_side[i]] = t[b.l_side[i]] = t[a.r_side[i]] = t[b.r_side[i]] = 0;
    d[a.l_side[i]] = d[b.l_side[i]] = d[a.r_side[i]] = d[b.r_side[i]] = 0;
  }
  merges = 0;
  for (int i = 1; i <= n; ++i) {
    if (v[a.r][i] == v[b.l][i]) {
      unite(a.r_side[i], b.l_side[i]);
    }
  }
  for (int i = 1; i <= n; ++i) {
    res.l_side[i] = parent(a.l_side[i]);
    res.r_side[i] = parent(b.r_side[i]);
  }
  res.cnt = a.cnt + b.cnt - merges;
  return res;
}
Segment calc[kMaxN];
int to[kMaxN], total;
Segment& Query(int i, int j) {
  if (j > to[i]) {
    calc[i] = Compose(calc[i], Query(to[i] + 1, j));
    to[i] = j;
  }
  return calc[i];
}
template <int cap = 1000000>
class Parser {
  char s[cap];
  int p, len;
  FILE* f;
  char get_char() {
    if (p == len) {
      fread(s, 1, cap - 1, f);
      s[cap - 1] = 0;
      len = strlen(s);
      p = 0;
    }
    char c = s[p];
    ++p;
    return c;
  }

 public:
  Parser(FILE* f = stdin) : f(f) {
    p = 0;
    len = 0;
  }
  Parser& operator>>(int& x) {
    char c;
    while (isspace(c = get_char()))
      ;
    x = c - '0';
    while (!isspace(c = get_char())) {
      x = x * 10 + c - '0';
    }
    return *this;
  }
};
void Solve() {
  Parser<10> in;
  in >> n >> m >> Q;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      in >> v[j][i];
    }
  }
  for (int i = 1; i <= Q; ++i) {
    in >> q[i].l >> q[i].r;
    q[i].i = i;
  }
  sort(q + 1, q + Q + 1);
  for (int i = 1; i <= m; ++i) {
    calc[i] = Segment(i);
    to[i] = i;
  }
  for (int i = 1; i <= Q; ++i) {
    ans[q[i].i] = Query(q[i].l, q[i].r).cnt;
  }
  for (int i = 1; i <= Q; ++i) {
    cout << ans[i] << "\n";
  }
}
void Reset() {}
int main() {
  int tests = 1;
  for (; tests; --tests) {
    Solve();
    Reset();
  }
}

### 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>
using namespace std;
const int kInf = (1 << 20);
const int kSq = 330;
const int kMaxN = 1e5 + 10;
int n, m, Q;
int v[kMaxN][12];
struct Query {
  int l, r, i;
  bool operator<(const Query& other) const { return r < other.r; }
} q[kMaxN];
int ans[kMaxN];
int t[11 * kMaxN], d[11 * kMaxN];
int merges;
int parent(int a) {
  if (t[a]) {
    return t[a] = parent(t[a]);
  }
  return a;
}
void unite(int a, int b) {
  a = parent(a);
  b = parent(b);
  if (a == b) return;
  ++merges;
  if (d[a] < d[b]) {
    t[a] = b;
  } else {
    t[b] = a;
    if (d[a] == d[b]) {
      ++d[a];
    }
  }
}
struct Segment {
  int l, r;
  vector<int> l_side, r_side;
  int cnt;
  Segment() {
    l_side.resize(n + 1);
    r_side.resize(n + 1);
  }
  Segment(int j) : l(j), r(j) {
    l_side.resize(n + 1);
    r_side.resize(n + 1);
    cnt = 0;
    for (int i = 1; i <= n; ++i) {
      if (i != 1 && v[l][i] == v[l][i - 1]) {
        l_side[i] = l_side[i - 1];
        r_side[i] = r_side[i - 1];
      } else {
        ++cnt;
        l_side[i] = (j - 1) * n + i;
        r_side[i] = (j - 1) * n + i;
      }
    }
  }
};
Segment Compose(const Segment& a, const Segment& b) {
  Segment res;
  res.l = a.l;
  res.r = b.r;
  for (int i = 1; i <= n; ++i) {
    t[a.l_side[i]] = t[b.l_side[i]] = t[a.r_side[i]] = t[b.r_side[i]] = 0;
    d[a.l_side[i]] = d[b.l_side[i]] = d[a.r_side[i]] = d[b.r_side[i]] = 0;
  }
  merges = 0;
  for (int i = 1; i <= n; ++i) {
    if (v[a.r][i] == v[b.l][i]) {
      unite(a.r_side[i], b.l_side[i]);
    }
  }
  for (int i = 1; i <= n; ++i) {
    res.l_side[i] = parent(a.l_side[i]);
    res.r_side[i] = parent(b.r_side[i]);
  }
  res.cnt = a.cnt + b.cnt - merges;
  return res;
}
Segment calc[kMaxN];
int to[kMaxN], total;
Segment& Query(int i, int j) {
  if (j > to[i]) {
    calc[i] = Compose(calc[i], Query(to[i] + 1, j));
    to[i] = j;
  }
  return calc[i];
}
template <int cap = 1000000>
class Parser {
  char s[cap];
  int p, len;
  FILE* f;
  char get_char() {
    if (p == len) {
      fread(s, 1, cap - 1, f);
      s[cap - 1] = 0;
      len = strlen(s);
      p = 0;
    }
    char c = s[p];
    ++p;
    return c;
  }

 public:
  Parser(FILE* f = stdin) : f(f) {
    p = 0;
    len = 0;
  }
  Parser& operator>>(int& x) {
    char c;
    while (isspace(c = get_char()))
      ;
    x = c - '0';
    while (!isspace(c = get_char())) {
      x = x * 10 + c - '0';
    }
    return *this;
  }
};
void Solve() {
  Parser<10> in;
  in >> n >> m >> Q;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= m; ++j) {
      in >> v[j][i];
    }
  }
  for (int i = 1; i <= Q; ++i) {
    in >> q[i].l >> q[i].r;
    q[i].i = i;
  }
  sort(q + 1, q + Q + 1);
  for (int i = 1; i <= m; ++i) {
    calc[i] = Segment(i);
    to[i] = i;
  }
  for (int i = 1; i <= Q; ++i) {
    ans[q[i].i] = Query(q[i].l, q[i].r).cnt;
  }
  for (int i = 1; i <= Q; ++i) {
    cout << ans[i] << "\n";
  }
}
void Reset() {}
int main() {
  int tests = 1;
  for (; tests; --tests) {
    Solve();
    Reset();
  }
}

```