#include <bits/stdc++.h>
std::string Name = "<stdin>";
std::string iput = Name.substr(0, Name.length() - 4) + ".in";
std::string oput = Name.substr(0, Name.length() - 4) + ".out";
template <class T>
inline bool chkmin(T &x, T y) {
  return x > y ? x = y, true : false;
}
template <class T>
inline bool chkmax(T &x, T y) {
  return x < y ? x = y, true : false;
}
template <class T>
inline T &read(T &x) {
  static int f;
  static char c;
  for (f = 1; !isdigit(c = getchar_unlocked());) {
    if (c == '-') f = -1;
  }
  for (x = 0; isdigit(c); c = getchar_unlocked()) {
    x = x * 10 + c - 48;
  }
  return x *= f;
}
template <class T>
inline void write(T x, const char p = '\n') {
  static int top;
  static int s[30];
  if (x < 0) {
    x = -x;
    putchar_unlocked('-');
  }
  do s[++top] = x % 10 + 48;
  while (x /= 10);
  while (top) putchar_unlocked(s[top--]);
  putchar_unlocked(p);
}
const int maxn = 1e5 + 5;
int n, m, q;
int cnt, fa[maxn * 11];
int num[11][maxn];
inline int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
struct node {
  int L[11], R[11], l, r, cnt;
  node() { cnt = -1; }
  node operator+(const node &a) const {
    if (cnt == -1) return a;
    if (a.cnt == -1) return *this;
    for (int i = 1; i <= n; ++i) {
      fa[L[i]] = L[i];
      fa[R[i]] = R[i];
      fa[a.L[i]] = a.L[i];
      fa[a.R[i]] = a.R[i];
    }
    node ret;
    ret.l = l;
    ret.r = a.r;
    ret.cnt = cnt + a.cnt;
    for (int i = 1; i <= n; ++i) {
      if (num[i][r] == num[i][a.l]) {
        int p = find(R[i]);
        int q = find(a.L[i]);
        if (p != q) --ret.cnt, fa[q] = p;
      }
    }
    for (int i = 1; i <= n; ++i) {
      ret.L[i] = find(L[i]);
      ret.R[i] = find(a.R[i]);
    }
    return ret;
  }
} s[maxn << 2];
void build(int x, int l, int r) {
  if (l == r) {
    s[x].cnt = 0;
    s[x].l = s[x].r = l;
    for (int i = 1; i <= n; ++i) {
      if (num[i][l] == num[i - 1][l]) {
        s[x].L[i] = s[x].R[i] = s[x].L[i - 1];
      } else {
        s[x].L[i] = s[x].R[i] = ++cnt;
        ++s[x].cnt;
      }
    }
    return;
  }
  int mid = l + r >> 1;
  build((x << 1), l, mid);
  build((x << 1 | 1), mid + 1, r);
  s[x] = s[(x << 1)] + s[(x << 1 | 1)];
}
node query(int x, int l, int r, int p, int q) {
  if (p <= l && r <= q) return s[x];
  int mid = l + r >> 1;
  if (q <= mid) return query((x << 1), l, mid, p, q);
  if (p > mid) return query((x << 1 | 1), mid + 1, r, p, q);
  return query((x << 1), l, mid, p, q) + query((x << 1 | 1), mid + 1, r, p, q);
}
void exec() {
  read(n), read(m), read(q);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) read(num[i][j]);
  build(1, 1, m);
  while (q--) {
    int l, r;
    read(l), read(r);
    write(query(1, 1, m, l, r).cnt);
  }
}
int main() {
  if (fopen(iput.c_str(), "r") != NULL) {
    freopen(iput.c_str(), "r", stdin);
    freopen(oput.c_str(), "w", stdout);
  }
  exec();
  fclose(stdin);
  fclose(stdout);
  return 0;
}

### Prompt

Generate 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>
std::string Name = "<stdin>";
std::string iput = Name.substr(0, Name.length() - 4) + ".in";
std::string oput = Name.substr(0, Name.length() - 4) + ".out";
template <class T>
inline bool chkmin(T &x, T y) {
  return x > y ? x = y, true : false;
}
template <class T>
inline bool chkmax(T &x, T y) {
  return x < y ? x = y, true : false;
}
template <class T>
inline T &read(T &x) {
  static int f;
  static char c;
  for (f = 1; !isdigit(c = getchar_unlocked());) {
    if (c == '-') f = -1;
  }
  for (x = 0; isdigit(c); c = getchar_unlocked()) {
    x = x * 10 + c - 48;
  }
  return x *= f;
}
template <class T>
inline void write(T x, const char p = '\n') {
  static int top;
  static int s[30];
  if (x < 0) {
    x = -x;
    putchar_unlocked('-');
  }
  do s[++top] = x % 10 + 48;
  while (x /= 10);
  while (top) putchar_unlocked(s[top--]);
  putchar_unlocked(p);
}
const int maxn = 1e5 + 5;
int n, m, q;
int cnt, fa[maxn * 11];
int num[11][maxn];
inline int find(int x) { return x == fa[x] ? x : fa[x] = find(fa[x]); }
struct node {
  int L[11], R[11], l, r, cnt;
  node() { cnt = -1; }
  node operator+(const node &a) const {
    if (cnt == -1) return a;
    if (a.cnt == -1) return *this;
    for (int i = 1; i <= n; ++i) {
      fa[L[i]] = L[i];
      fa[R[i]] = R[i];
      fa[a.L[i]] = a.L[i];
      fa[a.R[i]] = a.R[i];
    }
    node ret;
    ret.l = l;
    ret.r = a.r;
    ret.cnt = cnt + a.cnt;
    for (int i = 1; i <= n; ++i) {
      if (num[i][r] == num[i][a.l]) {
        int p = find(R[i]);
        int q = find(a.L[i]);
        if (p != q) --ret.cnt, fa[q] = p;
      }
    }
    for (int i = 1; i <= n; ++i) {
      ret.L[i] = find(L[i]);
      ret.R[i] = find(a.R[i]);
    }
    return ret;
  }
} s[maxn << 2];
void build(int x, int l, int r) {
  if (l == r) {
    s[x].cnt = 0;
    s[x].l = s[x].r = l;
    for (int i = 1; i <= n; ++i) {
      if (num[i][l] == num[i - 1][l]) {
        s[x].L[i] = s[x].R[i] = s[x].L[i - 1];
      } else {
        s[x].L[i] = s[x].R[i] = ++cnt;
        ++s[x].cnt;
      }
    }
    return;
  }
  int mid = l + r >> 1;
  build((x << 1), l, mid);
  build((x << 1 | 1), mid + 1, r);
  s[x] = s[(x << 1)] + s[(x << 1 | 1)];
}
node query(int x, int l, int r, int p, int q) {
  if (p <= l && r <= q) return s[x];
  int mid = l + r >> 1;
  if (q <= mid) return query((x << 1), l, mid, p, q);
  if (p > mid) return query((x << 1 | 1), mid + 1, r, p, q);
  return query((x << 1), l, mid, p, q) + query((x << 1 | 1), mid + 1, r, p, q);
}
void exec() {
  read(n), read(m), read(q);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) read(num[i][j]);
  build(1, 1, m);
  while (q--) {
    int l, r;
    read(l), read(r);
    write(query(1, 1, m, l, r).cnt);
  }
}
int main() {
  if (fopen(iput.c_str(), "r") != NULL) {
    freopen(iput.c_str(), "r", stdin);
    freopen(oput.c_str(), "w", stdout);
  }
  exec();
  fclose(stdin);
  fclose(stdout);
  return 0;
}

```