#include <bits/stdc++.h>
using namespace std;
int n, m, q, a[11][100005];
int comps[400005], lt[11][400005], rt[11][400005];
pair<int, int> par[3][1000001];
pair<int, int> par_find(pair<int, int> xp) {
  return par[xp.second][xp.first] == xp
             ? xp
             : par[xp.second][xp.first] = par_find(par[xp.second][xp.first]);
}
void build(int idx, int lo, int hi) {
  if (lo == hi) {
    for (int i = 1; i <= n; ++i) {
      if (a[i][lo] != a[i - 1][lo])
        lt[i][idx] = rt[i][idx] = ++comps[idx];
      else
        lt[i][idx] = rt[i][idx] = comps[idx];
    }
    return;
  }
  int mid = (lo + hi) / 2;
  build(2 * idx, lo, mid);
  build(2 * idx + 1, mid + 1, hi);
  comps[idx] = comps[2 * idx] + comps[2 * idx + 1];
  set<pair<int, int> > merged;
  for (int i = 1; i <= n; ++i) {
    int c1 = rt[i][2 * idx], c2 = lt[i][2 * idx + 1];
    if (a[i][mid] != a[i][mid + 1]) continue;
    if (merged.find(make_pair(c1, 1LL)) != merged.end()) {
      if (merged.find(make_pair(c2, 2LL)) != merged.end()) {
        pair<int, int> p1 = par_find(make_pair(c1, 1LL));
        pair<int, int> p2 = par_find(make_pair(c2, 2LL));
        par[p2.second][p2.first] = p1;
      } else {
        merged.insert(make_pair(c2, 2LL));
        par[2][c2] = par_find(make_pair(c1, 1LL));
      }
    } else {
      merged.insert(make_pair(c1, 1LL));
      par[1][c1] = make_pair(c1, 1LL);
      if (merged.find(make_pair(c2, 2LL)) != merged.end()) {
        pair<int, int> p1 = par_find(make_pair(c1, 1LL));
        pair<int, int> p2 = par_find(make_pair(c2, 2LL));
        par[p2.second][p2.first] = p1;
      } else {
        merged.insert(make_pair(c2, 2LL));
        par[2][c2] = par_find(make_pair(c1, 1LL));
      }
    }
  }
  comps[idx] -= merged.size();
  vector<pair<int, int> > skipped;
  for (pair<int, int> xp : merged) {
    if (par[xp.second][xp.first] == xp)
      comps[idx]++;
    else
      skipped.push_back(make_pair(xp.second, xp.first));
  }
  sort(skipped.begin(), skipped.end());
  for (int i = 1; i <= n; ++i) {
    int val = lt[i][2 * idx];
    pair<int, int> pf = make_pair(val, 1LL);
    if (merged.find(pf) != merged.end()) pf = par_find(make_pair(val, 1LL));
    int ps = lower_bound(skipped.begin(), skipped.end(),
                         make_pair(pf.second, pf.first)) -
             skipped.begin();
    if (skipped.empty()) ps = 0;
    if (pf.second == 1)
      lt[i][idx] = pf.first - ps;
    else
      lt[i][idx] = pf.first - ps + comps[2 * idx];
    val = rt[i][2 * idx + 1];
    pf = make_pair(val, 2LL);
    if (merged.find(pf) != merged.end()) pf = par_find(make_pair(val, 2LL));
    ps = lower_bound(skipped.begin(), skipped.end(),
                     make_pair(pf.second, pf.first)) -
         skipped.begin();
    if (skipped.empty()) ps = 0;
    if (pf.second == 1)
      rt[i][idx] = pf.first - ps;
    else
      rt[i][idx] = pf.first - ps + comps[2 * idx];
  }
}
struct node {
  int ff;
  int lt[11], rt[11];
  node(int v1) { ff = v1; }
};
node query(int idx, int lo, int hi, int st, int en) {
  if (lo == st && hi == en) {
    node ret = node(comps[idx]);
    for (int i = 1; i <= n; ++i) ret.lt[i] = lt[i][idx], ret.rt[i] = rt[i][idx];
    return ret;
  }
  int mid = (lo + hi) / 2;
  if (en <= mid)
    return query(2 * idx, lo, mid, st, en);
  else if (st > mid)
    return query(2 * idx + 1, mid + 1, hi, st, en);
  node q1 = query(2 * idx, lo, mid, st, mid);
  node q2 = query(2 * idx + 1, mid + 1, hi, mid + 1, en);
  node ret = node(q1.ff + q2.ff);
  set<pair<int, int> > merged;
  for (int i = 1; i <= n; ++i) {
    int c1 = q1.rt[i], c2 = q2.lt[i];
    if (a[i][mid] != a[i][mid + 1]) continue;
    if (merged.find(make_pair(c1, 1LL)) != merged.end()) {
      if (merged.find(make_pair(c2, 2LL)) != merged.end()) {
        pair<int, int> p1 = par_find(make_pair(c1, 1LL));
        pair<int, int> p2 = par_find(make_pair(c2, 2LL));
        par[p2.second][p2.first] = p1;
      } else {
        merged.insert(make_pair(c2, 2LL));
        par[2][c2] = par_find(make_pair(c1, 1LL));
      }
    } else {
      merged.insert(make_pair(c1, 1LL));
      par[1][c1] = make_pair(c1, 1LL);
      if (merged.find(make_pair(c2, 2LL)) != merged.end()) {
        pair<int, int> p1 = par_find(make_pair(c1, 1LL));
        pair<int, int> p2 = par_find(make_pair(c2, 2LL));
        par[p2.second][p2.first] = p1;
      } else {
        merged.insert(make_pair(c2, 2LL));
        par[2][c2] = par_find(make_pair(c1, 1LL));
      }
    }
  }
  ret.ff -= merged.size();
  vector<pair<int, int> > skipped;
  for (pair<int, int> xp : merged) {
    if (par[xp.second][xp.first] == xp)
      ret.ff++;
    else
      skipped.push_back(make_pair(xp.second, xp.first));
  }
  sort(skipped.begin(), skipped.end());
  for (int i = 1; i <= n; ++i) {
    int val = q1.lt[i];
    pair<int, int> pf = make_pair(val, 1LL);
    if (merged.find(pf) != merged.end()) pf = par_find(make_pair(val, 1LL));
    int ps = lower_bound(skipped.begin(), skipped.end(),
                         make_pair(pf.second, pf.first)) -
             skipped.begin();
    if (skipped.empty()) ps = 0;
    if (pf.second == 1)
      ret.lt[i] = pf.first - ps;
    else
      ret.lt[i] = pf.first - ps + q1.ff;
    val = q2.rt[i];
    pf = make_pair(val, 2LL);
    if (merged.find(pf) != merged.end()) pf = par_find(make_pair(val, 2LL));
    ps = lower_bound(skipped.begin(), skipped.end(),
                     make_pair(pf.second, pf.first)) -
         skipped.begin();
    if (skipped.empty()) ps = 0;
    if (pf.second == 1)
      ret.rt[i] = pf.first - ps;
    else
      ret.rt[i] = pf.first - ps + q1.ff;
  }
  return ret;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m >> q;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) cin >> a[i][j];
  build(1, 1, m);
  while (q--) {
    int l, r;
    cin >> l >> r;
    cout << query(1, 1, m, l, r).ff << '\n';
  }
}

### 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>
using namespace std;
int n, m, q, a[11][100005];
int comps[400005], lt[11][400005], rt[11][400005];
pair<int, int> par[3][1000001];
pair<int, int> par_find(pair<int, int> xp) {
  return par[xp.second][xp.first] == xp
             ? xp
             : par[xp.second][xp.first] = par_find(par[xp.second][xp.first]);
}
void build(int idx, int lo, int hi) {
  if (lo == hi) {
    for (int i = 1; i <= n; ++i) {
      if (a[i][lo] != a[i - 1][lo])
        lt[i][idx] = rt[i][idx] = ++comps[idx];
      else
        lt[i][idx] = rt[i][idx] = comps[idx];
    }
    return;
  }
  int mid = (lo + hi) / 2;
  build(2 * idx, lo, mid);
  build(2 * idx + 1, mid + 1, hi);
  comps[idx] = comps[2 * idx] + comps[2 * idx + 1];
  set<pair<int, int> > merged;
  for (int i = 1; i <= n; ++i) {
    int c1 = rt[i][2 * idx], c2 = lt[i][2 * idx + 1];
    if (a[i][mid] != a[i][mid + 1]) continue;
    if (merged.find(make_pair(c1, 1LL)) != merged.end()) {
      if (merged.find(make_pair(c2, 2LL)) != merged.end()) {
        pair<int, int> p1 = par_find(make_pair(c1, 1LL));
        pair<int, int> p2 = par_find(make_pair(c2, 2LL));
        par[p2.second][p2.first] = p1;
      } else {
        merged.insert(make_pair(c2, 2LL));
        par[2][c2] = par_find(make_pair(c1, 1LL));
      }
    } else {
      merged.insert(make_pair(c1, 1LL));
      par[1][c1] = make_pair(c1, 1LL);
      if (merged.find(make_pair(c2, 2LL)) != merged.end()) {
        pair<int, int> p1 = par_find(make_pair(c1, 1LL));
        pair<int, int> p2 = par_find(make_pair(c2, 2LL));
        par[p2.second][p2.first] = p1;
      } else {
        merged.insert(make_pair(c2, 2LL));
        par[2][c2] = par_find(make_pair(c1, 1LL));
      }
    }
  }
  comps[idx] -= merged.size();
  vector<pair<int, int> > skipped;
  for (pair<int, int> xp : merged) {
    if (par[xp.second][xp.first] == xp)
      comps[idx]++;
    else
      skipped.push_back(make_pair(xp.second, xp.first));
  }
  sort(skipped.begin(), skipped.end());
  for (int i = 1; i <= n; ++i) {
    int val = lt[i][2 * idx];
    pair<int, int> pf = make_pair(val, 1LL);
    if (merged.find(pf) != merged.end()) pf = par_find(make_pair(val, 1LL));
    int ps = lower_bound(skipped.begin(), skipped.end(),
                         make_pair(pf.second, pf.first)) -
             skipped.begin();
    if (skipped.empty()) ps = 0;
    if (pf.second == 1)
      lt[i][idx] = pf.first - ps;
    else
      lt[i][idx] = pf.first - ps + comps[2 * idx];
    val = rt[i][2 * idx + 1];
    pf = make_pair(val, 2LL);
    if (merged.find(pf) != merged.end()) pf = par_find(make_pair(val, 2LL));
    ps = lower_bound(skipped.begin(), skipped.end(),
                     make_pair(pf.second, pf.first)) -
         skipped.begin();
    if (skipped.empty()) ps = 0;
    if (pf.second == 1)
      rt[i][idx] = pf.first - ps;
    else
      rt[i][idx] = pf.first - ps + comps[2 * idx];
  }
}
struct node {
  int ff;
  int lt[11], rt[11];
  node(int v1) { ff = v1; }
};
node query(int idx, int lo, int hi, int st, int en) {
  if (lo == st && hi == en) {
    node ret = node(comps[idx]);
    for (int i = 1; i <= n; ++i) ret.lt[i] = lt[i][idx], ret.rt[i] = rt[i][idx];
    return ret;
  }
  int mid = (lo + hi) / 2;
  if (en <= mid)
    return query(2 * idx, lo, mid, st, en);
  else if (st > mid)
    return query(2 * idx + 1, mid + 1, hi, st, en);
  node q1 = query(2 * idx, lo, mid, st, mid);
  node q2 = query(2 * idx + 1, mid + 1, hi, mid + 1, en);
  node ret = node(q1.ff + q2.ff);
  set<pair<int, int> > merged;
  for (int i = 1; i <= n; ++i) {
    int c1 = q1.rt[i], c2 = q2.lt[i];
    if (a[i][mid] != a[i][mid + 1]) continue;
    if (merged.find(make_pair(c1, 1LL)) != merged.end()) {
      if (merged.find(make_pair(c2, 2LL)) != merged.end()) {
        pair<int, int> p1 = par_find(make_pair(c1, 1LL));
        pair<int, int> p2 = par_find(make_pair(c2, 2LL));
        par[p2.second][p2.first] = p1;
      } else {
        merged.insert(make_pair(c2, 2LL));
        par[2][c2] = par_find(make_pair(c1, 1LL));
      }
    } else {
      merged.insert(make_pair(c1, 1LL));
      par[1][c1] = make_pair(c1, 1LL);
      if (merged.find(make_pair(c2, 2LL)) != merged.end()) {
        pair<int, int> p1 = par_find(make_pair(c1, 1LL));
        pair<int, int> p2 = par_find(make_pair(c2, 2LL));
        par[p2.second][p2.first] = p1;
      } else {
        merged.insert(make_pair(c2, 2LL));
        par[2][c2] = par_find(make_pair(c1, 1LL));
      }
    }
  }
  ret.ff -= merged.size();
  vector<pair<int, int> > skipped;
  for (pair<int, int> xp : merged) {
    if (par[xp.second][xp.first] == xp)
      ret.ff++;
    else
      skipped.push_back(make_pair(xp.second, xp.first));
  }
  sort(skipped.begin(), skipped.end());
  for (int i = 1; i <= n; ++i) {
    int val = q1.lt[i];
    pair<int, int> pf = make_pair(val, 1LL);
    if (merged.find(pf) != merged.end()) pf = par_find(make_pair(val, 1LL));
    int ps = lower_bound(skipped.begin(), skipped.end(),
                         make_pair(pf.second, pf.first)) -
             skipped.begin();
    if (skipped.empty()) ps = 0;
    if (pf.second == 1)
      ret.lt[i] = pf.first - ps;
    else
      ret.lt[i] = pf.first - ps + q1.ff;
    val = q2.rt[i];
    pf = make_pair(val, 2LL);
    if (merged.find(pf) != merged.end()) pf = par_find(make_pair(val, 2LL));
    ps = lower_bound(skipped.begin(), skipped.end(),
                     make_pair(pf.second, pf.first)) -
         skipped.begin();
    if (skipped.empty()) ps = 0;
    if (pf.second == 1)
      ret.rt[i] = pf.first - ps;
    else
      ret.rt[i] = pf.first - ps + q1.ff;
  }
  return ret;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cin >> n >> m >> q;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) cin >> a[i][j];
  build(1, 1, m);
  while (q--) {
    int l, r;
    cin >> l >> r;
    cout << query(1, 1, m, l, r).ff << '\n';
  }
}

```