#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 1123456;
template <typename T>
T sqr(T x) {
  return x * x;
}
template <typename T>
void vout(T s) {
  cout << s << "\n";
  exit(0);
}
long long bp(long long a, long long n) {
  long long res = 1;
  while (n) {
    if (n % 2) res *= a;
    a *= a;
    n >>= 1;
  }
  return res;
}
vector<long long> v[MAXN], va;
string s1, s2, s3;
set<long long> s;
char cc;
long long a[11][100001], b[MAXN], c, a1, b1, c1, i, j, n, m, k, ans, sc, x;
long long ke[MAXN];
long long zp[MAXN];
long long zapros = 0;
long long sn[41];
long long get(long long x) {
  if (sn[x] != x) sn[x] = get(sn[x]);
  return sn[x];
}
bool fl = 0;
bool kke;
long long te, ti;
struct be {
  long long len = 0;
  long long lp[11], rp[11], kl = 0, lsn[11], rsn[11];
  be() {}
  be(be l, be r) {
    zapros++;
    long long i;
    for (i = 1; i < 41; i++) sn[i] = i;
    long long ku = 0;
    long long le[11], ri[11], lk[11], rk[11];
    for (i = 1; i <= n; i++) lsn[i] = l.lsn[i], rsn[i] = r.rsn[i];
    for (i = 1; i <= n; i++) lp[i] = l.lp[i], rp[i] = r.rp[i];
    kl = l.kl + r.kl;
    len = l.len + r.len;
    if (r.kl && l.kl) {
      for (i = 1; i <= n; i++) {
        if (zp[l.rsn[i]] != zapros) {
          ku++;
          ke[l.rsn[i]] = ku;
          zp[l.rsn[i]] = zapros;
        }
        le[i] = ke[l.rsn[i]];
      }
      for (i = 1; i <= n; i++) {
        if (zp[l.lsn[i]] != zapros) {
          ku++;
          ke[l.lsn[i]] = ku;
          zp[l.lsn[i]] = zapros;
        }
        lk[i] = ke[l.lsn[i]];
      }
      zapros++;
      for (i = 1; i <= n; i++) {
        if (zp[r.lsn[i]] != zapros) {
          ku++;
          zp[r.lsn[i]] = zapros;
          ke[r.lsn[i]] = ku;
        }
        ri[i] = ke[r.lsn[i]];
      }
      for (i = 1; i <= n; i++) {
        if (zp[r.rsn[i]] != zapros) {
          ku++;
          zp[r.rsn[i]] = zapros;
          ke[r.rsn[i]] = ku;
        }
        rk[i] = ke[r.rsn[i]];
      }
      for (i = 1; i <= n; i++)
        if (l.rp[i] == r.lp[i] && get(le[i]) != get(ri[i])) {
          sn[get(le[i])] = get(ri[i]);
          kl--;
        }
      for (i = 1; i <= n; i++) lsn[i] = get(lk[i]);
      for (i = 1; i <= n; i++) rsn[i] = get(rk[i]);
    }
  }
};
be p[500000];
be xe;
void build(long long v, long long tl, long long tr) {
  long long i;
  if (tl == tr) {
    long long i;
    p[v].len = 1;
    for (i = 1; i <= n; i++) p[v].lp[i] = p[v].rp[i] = a[i][tl];
    long long stn = 1;
    p[v].lsn[1] = p[v].rsn[1] = 1;
    for (i = 2; i <= n; i++) {
      p[v].lsn[i] = p[v].rsn[i] = p[v].lsn[i - 1];
      if (a[i][tl] != a[i - 1][tl]) {
        stn++;
        p[v].lsn[i] = p[v].rsn[i] = stn;
      }
    }
    p[v].kl = stn;
  } else {
    long long tm = (tl + tr) >> 1;
    build(v << 1, tl, tm);
    build((v << 1) + 1, tm + 1, tr);
    p[v] = be(p[v << 1], p[(v << 1) + 1]);
  }
}
be gget(long long v, long long tl, long long tr, long long l, long long r) {
  kke = fl;
  if (l > r) return xe;
  if (tl == l && tr == r) return p[v];
  long long tm = (tl + tr) >> 1;
  return be(gget(v << 1, tl, tm, l, min(r, tm)),
            gget((v << 1) + 1, tm + 1, tr, max(l, tm + 1), r));
}
int main() {
  ios_base ::sync_with_stdio(0);
  cin.tie(0);
  long long q;
  cin >> n >> m >> q;
  for (i = 1; i <= n; i++)
    for (j = 1; j <= m; j++) cin >> a[i][j];
  build(1, 1, m);
  while (q--) {
    long long l, r;
    cin >> l >> r;
    cout << gget(1, 1, m, l, r).kl << "\n";
  }
  return 0;
}

### Prompt

Construct a CPP code solution to the problem outlined:

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 long long MAXN = 1123456;
template <typename T>
T sqr(T x) {
  return x * x;
}
template <typename T>
void vout(T s) {
  cout << s << "\n";
  exit(0);
}
long long bp(long long a, long long n) {
  long long res = 1;
  while (n) {
    if (n % 2) res *= a;
    a *= a;
    n >>= 1;
  }
  return res;
}
vector<long long> v[MAXN], va;
string s1, s2, s3;
set<long long> s;
char cc;
long long a[11][100001], b[MAXN], c, a1, b1, c1, i, j, n, m, k, ans, sc, x;
long long ke[MAXN];
long long zp[MAXN];
long long zapros = 0;
long long sn[41];
long long get(long long x) {
  if (sn[x] != x) sn[x] = get(sn[x]);
  return sn[x];
}
bool fl = 0;
bool kke;
long long te, ti;
struct be {
  long long len = 0;
  long long lp[11], rp[11], kl = 0, lsn[11], rsn[11];
  be() {}
  be(be l, be r) {
    zapros++;
    long long i;
    for (i = 1; i < 41; i++) sn[i] = i;
    long long ku = 0;
    long long le[11], ri[11], lk[11], rk[11];
    for (i = 1; i <= n; i++) lsn[i] = l.lsn[i], rsn[i] = r.rsn[i];
    for (i = 1; i <= n; i++) lp[i] = l.lp[i], rp[i] = r.rp[i];
    kl = l.kl + r.kl;
    len = l.len + r.len;
    if (r.kl && l.kl) {
      for (i = 1; i <= n; i++) {
        if (zp[l.rsn[i]] != zapros) {
          ku++;
          ke[l.rsn[i]] = ku;
          zp[l.rsn[i]] = zapros;
        }
        le[i] = ke[l.rsn[i]];
      }
      for (i = 1; i <= n; i++) {
        if (zp[l.lsn[i]] != zapros) {
          ku++;
          ke[l.lsn[i]] = ku;
          zp[l.lsn[i]] = zapros;
        }
        lk[i] = ke[l.lsn[i]];
      }
      zapros++;
      for (i = 1; i <= n; i++) {
        if (zp[r.lsn[i]] != zapros) {
          ku++;
          zp[r.lsn[i]] = zapros;
          ke[r.lsn[i]] = ku;
        }
        ri[i] = ke[r.lsn[i]];
      }
      for (i = 1; i <= n; i++) {
        if (zp[r.rsn[i]] != zapros) {
          ku++;
          zp[r.rsn[i]] = zapros;
          ke[r.rsn[i]] = ku;
        }
        rk[i] = ke[r.rsn[i]];
      }
      for (i = 1; i <= n; i++)
        if (l.rp[i] == r.lp[i] && get(le[i]) != get(ri[i])) {
          sn[get(le[i])] = get(ri[i]);
          kl--;
        }
      for (i = 1; i <= n; i++) lsn[i] = get(lk[i]);
      for (i = 1; i <= n; i++) rsn[i] = get(rk[i]);
    }
  }
};
be p[500000];
be xe;
void build(long long v, long long tl, long long tr) {
  long long i;
  if (tl == tr) {
    long long i;
    p[v].len = 1;
    for (i = 1; i <= n; i++) p[v].lp[i] = p[v].rp[i] = a[i][tl];
    long long stn = 1;
    p[v].lsn[1] = p[v].rsn[1] = 1;
    for (i = 2; i <= n; i++) {
      p[v].lsn[i] = p[v].rsn[i] = p[v].lsn[i - 1];
      if (a[i][tl] != a[i - 1][tl]) {
        stn++;
        p[v].lsn[i] = p[v].rsn[i] = stn;
      }
    }
    p[v].kl = stn;
  } else {
    long long tm = (tl + tr) >> 1;
    build(v << 1, tl, tm);
    build((v << 1) + 1, tm + 1, tr);
    p[v] = be(p[v << 1], p[(v << 1) + 1]);
  }
}
be gget(long long v, long long tl, long long tr, long long l, long long r) {
  kke = fl;
  if (l > r) return xe;
  if (tl == l && tr == r) return p[v];
  long long tm = (tl + tr) >> 1;
  return be(gget(v << 1, tl, tm, l, min(r, tm)),
            gget((v << 1) + 1, tm + 1, tr, max(l, tm + 1), r));
}
int main() {
  ios_base ::sync_with_stdio(0);
  cin.tie(0);
  long long q;
  cin >> n >> m >> q;
  for (i = 1; i <= n; i++)
    for (j = 1; j <= m; j++) cin >> a[i][j];
  build(1, 1, m);
  while (q--) {
    long long l, r;
    cin >> l >> r;
    cout << gget(1, 1, m, l, r).kl << "\n";
  }
  return 0;
}

```