#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;
const long long MXN = 45;
const long long MXM = 1e5 + 10;
const long long MXS = MXM * 4;
int n, m, q;
struct Data {
  int ans;
  int L[MXN], R[MXN];
  Data() {
    ans = 0;
    memset(L, 0, sizeof L);
    memset(R, 0, sizeof R);
  }
};
int C[MXN][MXM], Par[MXM], Sz[MXM];
Data seg[MXS];
Data Comp(Data a) {
  vector<int> v;
  for (int i = 1; i <= n; i++) v.push_back(a.L[i]);
  for (int i = 1; i <= n; i++) v.push_back(a.R[i]);
  sort(v.begin(), v.end());
  v.resize(unique(v.begin(), v.end()) - v.begin());
  for (int i = 1; i <= n; i++) {
    a.L[i] = (lower_bound(v.begin(), v.end(), a.L[i]) - v.begin()) + 1;
    a.R[i] = (lower_bound(v.begin(), v.end(), a.R[i]) - v.begin()) + 1;
  }
  return a;
}
int Find(int x) { return (Par[x] == x ? x : Par[x] = Find(Par[x])); }
bool Union(int x, int y) {
  x = Find(x), y = Find(y);
  if (x == y) return 0;
  if (Sz[x] < Sz[y]) swap(x, y);
  Sz[x] += Sz[y], Par[y] = x;
  return 1;
}
Data Merge(Data a, Data b, int p) {
  Data c;
  c.ans = a.ans + b.ans;
  for (int i = 1; i < MXN; i++) {
    Par[i] = i, Sz[i] = 1;
  }
  for (int i = 1; i <= n; i++) {
    b.L[i] += 2 * n, b.R[i] += 2 * n;
  }
  for (int i = 1; i <= n; i++) {
    if (C[i][p] == C[i][p + 1]) {
      c.ans -= Union(a.R[i], b.L[i]);
    }
  }
  for (int i = 1; i <= n; i++) {
    c.L[i] = Find(a.L[i]);
    c.R[i] = Find(b.R[i]);
  }
  c = Comp(c);
  return c;
}
void Build(int id = 1, int s = 1, int e = m) {
  if ((e - s + 1) == 1) {
    int last = 1;
    seg[id].L[1] = seg[id].R[1] = 1;
    for (int i = 2; i <= n; i++) {
      if (C[i - 1][s] != C[i][s]) {
        last++;
      }
      seg[id].L[i] = seg[id].R[i] = last;
    }
    seg[id].ans = last;
    return;
  }
  Build((id * 2), s, ((s + e) / 2)), Build((id * 2 + 1), ((s + e) / 2 + 1), e);
  seg[id] = Merge(seg[(id * 2)], seg[(id * 2 + 1)], ((s + e) / 2));
}
Data Get(int l, int r, int id = 1, int s = 1, int e = m) {
  if (l <= s && e <= r) return seg[id];
  if (r <= ((s + e) / 2)) return Get(l, r, (id * 2), s, ((s + e) / 2));
  if (l >= ((s + e) / 2 + 1))
    return Get(l, r, (id * 2 + 1), ((s + e) / 2 + 1), e);
  return Merge(Get(l, r, (id * 2), s, ((s + e) / 2)),
               Get(l, r, (id * 2 + 1), ((s + e) / 2 + 1), e), ((s + e) / 2));
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m >> q;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) cin >> C[i][j];
  }
  Build();
  while (q--) {
    long long l, r;
    cin >> l >> r;
    cout << Get(l, r).ans << '\n';
  }
  return 0;
}

### Prompt

Your challenge is to write 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>
#pragma GCC optimize("O2")
using namespace std;
const long long MXN = 45;
const long long MXM = 1e5 + 10;
const long long MXS = MXM * 4;
int n, m, q;
struct Data {
  int ans;
  int L[MXN], R[MXN];
  Data() {
    ans = 0;
    memset(L, 0, sizeof L);
    memset(R, 0, sizeof R);
  }
};
int C[MXN][MXM], Par[MXM], Sz[MXM];
Data seg[MXS];
Data Comp(Data a) {
  vector<int> v;
  for (int i = 1; i <= n; i++) v.push_back(a.L[i]);
  for (int i = 1; i <= n; i++) v.push_back(a.R[i]);
  sort(v.begin(), v.end());
  v.resize(unique(v.begin(), v.end()) - v.begin());
  for (int i = 1; i <= n; i++) {
    a.L[i] = (lower_bound(v.begin(), v.end(), a.L[i]) - v.begin()) + 1;
    a.R[i] = (lower_bound(v.begin(), v.end(), a.R[i]) - v.begin()) + 1;
  }
  return a;
}
int Find(int x) { return (Par[x] == x ? x : Par[x] = Find(Par[x])); }
bool Union(int x, int y) {
  x = Find(x), y = Find(y);
  if (x == y) return 0;
  if (Sz[x] < Sz[y]) swap(x, y);
  Sz[x] += Sz[y], Par[y] = x;
  return 1;
}
Data Merge(Data a, Data b, int p) {
  Data c;
  c.ans = a.ans + b.ans;
  for (int i = 1; i < MXN; i++) {
    Par[i] = i, Sz[i] = 1;
  }
  for (int i = 1; i <= n; i++) {
    b.L[i] += 2 * n, b.R[i] += 2 * n;
  }
  for (int i = 1; i <= n; i++) {
    if (C[i][p] == C[i][p + 1]) {
      c.ans -= Union(a.R[i], b.L[i]);
    }
  }
  for (int i = 1; i <= n; i++) {
    c.L[i] = Find(a.L[i]);
    c.R[i] = Find(b.R[i]);
  }
  c = Comp(c);
  return c;
}
void Build(int id = 1, int s = 1, int e = m) {
  if ((e - s + 1) == 1) {
    int last = 1;
    seg[id].L[1] = seg[id].R[1] = 1;
    for (int i = 2; i <= n; i++) {
      if (C[i - 1][s] != C[i][s]) {
        last++;
      }
      seg[id].L[i] = seg[id].R[i] = last;
    }
    seg[id].ans = last;
    return;
  }
  Build((id * 2), s, ((s + e) / 2)), Build((id * 2 + 1), ((s + e) / 2 + 1), e);
  seg[id] = Merge(seg[(id * 2)], seg[(id * 2 + 1)], ((s + e) / 2));
}
Data Get(int l, int r, int id = 1, int s = 1, int e = m) {
  if (l <= s && e <= r) return seg[id];
  if (r <= ((s + e) / 2)) return Get(l, r, (id * 2), s, ((s + e) / 2));
  if (l >= ((s + e) / 2 + 1))
    return Get(l, r, (id * 2 + 1), ((s + e) / 2 + 1), e);
  return Merge(Get(l, r, (id * 2), s, ((s + e) / 2)),
               Get(l, r, (id * 2 + 1), ((s + e) / 2 + 1), e), ((s + e) / 2));
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m >> q;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) cin >> C[i][j];
  }
  Build();
  while (q--) {
    long long l, r;
    cin >> l >> r;
    cout << Get(l, r).ans << '\n';
  }
  return 0;
}

```