#include <bits/stdc++.h>
using namespace std;
template <class T>
inline bool cmin(T& a, T b) {
  return a > b ? a = b, true : false;
}
template <class T>
inline bool cmax(T& a, T b) {
  return a < b ? a = b, true : false;
}
template <class T>
inline T squ(T a) {
  return a * a;
}
const int maxn = 400000 + 10, base = 23, mod = 1000000007, limit = 400020,
          inf = 20000000;
int read() {
  int x = 0, f = 1, ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
  return x * f;
}
int n, m, v[12][maxn], Q;
int cnt = 0;
int fa[2020000];
int getfa(int x) { return x == fa[x] ? x : fa[x] = getfa(fa[x]); }
struct node {
  int sum, L[12], R[12], l, r;
  friend node operator+(const node& a, const node& b) {
    if (!a.L[1]) return b;
    if (!b.L[1]) return a;
    node c;
    c.sum = a.sum + b.sum;
    for (int i = (1); i <= (n); i++)
      fa[a.L[i]] = a.L[i], fa[a.R[i]] = a.R[i], fa[b.L[i]] = b.L[i],
      fa[b.R[i]] = b.R[i];
    for (int i = (1); i <= (n); i++)
      if (v[i][a.r] == v[i][a.r + 1]) {
        int fx = getfa(a.R[i]), fy = getfa(b.L[i]);
        if (fx != fy) {
          fa[fx] = fy;
          c.sum--;
        }
      }
    for (int i = (1); i <= (n); i++)
      c.L[i] = getfa(a.L[i]), c.R[i] = getfa(b.R[i]);
    c.l = a.l;
    c.r = b.r;
    return c;
  }
} a[maxn], null;
void build(int o, int l, int r) {
  if (l == r) {
    for (int i = (1); i <= (n); i++)
      if (v[i][l] == v[i - 1][l])
        a[o].L[i] = a[o].R[i] = a[o].L[i - 1];
      else
        a[o].L[i] = a[o].R[i] = ++cnt, a[o].sum++;
    a[o].l = l, a[o].r = r;
    return;
  }
  int mid = (l + r) >> 1;
  build(o << 1, l, mid);
  build(o << 1 | 1, mid + 1, r);
  a[o] = a[o << 1] + a[o << 1 | 1];
}
node query(int o, int L, int R, int l, int r) {
  if (l > R || r < L) return null;
  if (l >= L && r <= R) return a[o];
  int mid = (l + r) >> 1;
  return query(o << 1, L, R, l, mid) + query(o << 1 | 1, L, R, mid + 1, r);
}
int main() {
  n = read(), m = read(), Q = read();
  for (int i = (1); i <= (n); i++)
    for (int j = (1); j <= (m); j++) v[i][j] = read();
  build(1, 1, m);
  for (int i = (1); i <= (Q); i++) {
    int x = read(), y = read();
    printf("%d\n", query(1, x, y, 1, m).sum);
  }
  return 0;
}

### Prompt

Please create a solution in CPP 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;
template <class T>
inline bool cmin(T& a, T b) {
  return a > b ? a = b, true : false;
}
template <class T>
inline bool cmax(T& a, T b) {
  return a < b ? a = b, true : false;
}
template <class T>
inline T squ(T a) {
  return a * a;
}
const int maxn = 400000 + 10, base = 23, mod = 1000000007, limit = 400020,
          inf = 20000000;
int read() {
  int x = 0, f = 1, ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9')
    x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
  return x * f;
}
int n, m, v[12][maxn], Q;
int cnt = 0;
int fa[2020000];
int getfa(int x) { return x == fa[x] ? x : fa[x] = getfa(fa[x]); }
struct node {
  int sum, L[12], R[12], l, r;
  friend node operator+(const node& a, const node& b) {
    if (!a.L[1]) return b;
    if (!b.L[1]) return a;
    node c;
    c.sum = a.sum + b.sum;
    for (int i = (1); i <= (n); i++)
      fa[a.L[i]] = a.L[i], fa[a.R[i]] = a.R[i], fa[b.L[i]] = b.L[i],
      fa[b.R[i]] = b.R[i];
    for (int i = (1); i <= (n); i++)
      if (v[i][a.r] == v[i][a.r + 1]) {
        int fx = getfa(a.R[i]), fy = getfa(b.L[i]);
        if (fx != fy) {
          fa[fx] = fy;
          c.sum--;
        }
      }
    for (int i = (1); i <= (n); i++)
      c.L[i] = getfa(a.L[i]), c.R[i] = getfa(b.R[i]);
    c.l = a.l;
    c.r = b.r;
    return c;
  }
} a[maxn], null;
void build(int o, int l, int r) {
  if (l == r) {
    for (int i = (1); i <= (n); i++)
      if (v[i][l] == v[i - 1][l])
        a[o].L[i] = a[o].R[i] = a[o].L[i - 1];
      else
        a[o].L[i] = a[o].R[i] = ++cnt, a[o].sum++;
    a[o].l = l, a[o].r = r;
    return;
  }
  int mid = (l + r) >> 1;
  build(o << 1, l, mid);
  build(o << 1 | 1, mid + 1, r);
  a[o] = a[o << 1] + a[o << 1 | 1];
}
node query(int o, int L, int R, int l, int r) {
  if (l > R || r < L) return null;
  if (l >= L && r <= R) return a[o];
  int mid = (l + r) >> 1;
  return query(o << 1, L, R, l, mid) + query(o << 1 | 1, L, R, mid + 1, r);
}
int main() {
  n = read(), m = read(), Q = read();
  for (int i = (1); i <= (n); i++)
    for (int j = (1); j <= (m); j++) v[i][j] = read();
  build(1, 1, m);
  for (int i = (1); i <= (Q); i++) {
    int x = read(), y = read();
    printf("%d\n", query(1, x, y, 1, m).sum);
  }
  return 0;
}

```