#include <bits/stdc++.h>
using namespace std;
const int N = 100050;
const int M = 2 * N;
int n, m;
int mat[N][10];
struct Node {
  int sol, ss, se;
  int lid[10], rid[10], nid;
  Node() {}
} node[M];
struct DSU {
  int p[40];
  DSU() {}
  void init() {
    for (int i = 0; i < 40; i++) p[i] = i;
  }
  int Find(int x) { return p[x] == x ? x : p[x] = Find(p[x]); }
  void Union(int x, int y) { p[Find(x)] = Find(y); }
} Tree;
Node Merge(Node a, Node b) {
  Node ans;
  ans.sol = a.sol + b.sol;
  ans.ss = a.ss;
  ans.se = b.se;
  ans.nid = a.nid + b.nid;
  int l = a.se, r = b.ss;
  for (int i = 0; i < n; i++) b.lid[i] += a.nid, b.rid[i] += a.nid;
  for (int i = 0; i < n; i++)
    if (a.rid[i] != b.lid[i] && mat[l][i] == mat[r][i]) {
      ans.sol--;
      int oid = b.lid[i];
      for (int j = 0; j < n; j++)
        if (a.lid[j] == oid) a.lid[j] = a.rid[i];
      for (int j = 0; j < n; j++)
        if (a.rid[j] == oid) a.rid[j] = a.rid[i];
      for (int j = 0; j < n; j++)
        if (b.lid[j] == oid) b.lid[j] = a.rid[i];
      for (int j = 0; j < n; j++)
        if (b.rid[j] == oid) b.rid[j] = a.rid[i];
    }
  for (int i = 0; i < n; i++) ans.lid[i] = a.lid[i], ans.rid[i] = b.rid[i];
  return ans;
}
int ls[M], rs[M], tsz, root;
void Build(int &c, int ss, int se) {
  c = ++tsz;
  if (ss == se) {
    int i, j;
    node[c].ss = node[c].se = ss;
    node[c].sol = node[c].nid = 0;
    for (i = 0; i < n; i = j) {
      for (j = i; j < n && mat[ss][j] == mat[ss][i]; j++)
        node[c].lid[j] = node[c].rid[j] = node[c].nid;
      node[c].nid++;
      node[c].sol++;
    }
    return;
  }
  int mid = ss + se >> 1;
  Build(ls[c], ss, mid);
  Build(rs[c], mid + 1, se);
  node[c] = Merge(node[ls[c]], node[rs[c]]);
}
Node Get(int c, int ss, int se, int qs, int qe) {
  if (qs <= ss && qe >= se) return node[c];
  int mid = ss + se >> 1;
  if (qe <= mid) return Get(ls[c], ss, mid, qs, qe);
  if (qs > mid) return Get(rs[c], mid + 1, se, qs, qe);
  return Merge(Get(ls[c], ss, mid, qs, qe), Get(rs[c], mid + 1, se, qs, qe));
}
int main() {
  int q, i, j, l, r;
  scanf("%i %i %i", &n, &m, &q);
  for (i = 0; i < n; i++)
    for (j = 1; j <= m; j++) scanf("%i", &mat[j][i]);
  Build(root, 1, m);
  while (q--) {
    scanf("%i %i", &l, &r);
    Node ans = Get(root, 1, m, l, r);
    printf("%i\n", ans.sol);
  }
  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;
const int N = 100050;
const int M = 2 * N;
int n, m;
int mat[N][10];
struct Node {
  int sol, ss, se;
  int lid[10], rid[10], nid;
  Node() {}
} node[M];
struct DSU {
  int p[40];
  DSU() {}
  void init() {
    for (int i = 0; i < 40; i++) p[i] = i;
  }
  int Find(int x) { return p[x] == x ? x : p[x] = Find(p[x]); }
  void Union(int x, int y) { p[Find(x)] = Find(y); }
} Tree;
Node Merge(Node a, Node b) {
  Node ans;
  ans.sol = a.sol + b.sol;
  ans.ss = a.ss;
  ans.se = b.se;
  ans.nid = a.nid + b.nid;
  int l = a.se, r = b.ss;
  for (int i = 0; i < n; i++) b.lid[i] += a.nid, b.rid[i] += a.nid;
  for (int i = 0; i < n; i++)
    if (a.rid[i] != b.lid[i] && mat[l][i] == mat[r][i]) {
      ans.sol--;
      int oid = b.lid[i];
      for (int j = 0; j < n; j++)
        if (a.lid[j] == oid) a.lid[j] = a.rid[i];
      for (int j = 0; j < n; j++)
        if (a.rid[j] == oid) a.rid[j] = a.rid[i];
      for (int j = 0; j < n; j++)
        if (b.lid[j] == oid) b.lid[j] = a.rid[i];
      for (int j = 0; j < n; j++)
        if (b.rid[j] == oid) b.rid[j] = a.rid[i];
    }
  for (int i = 0; i < n; i++) ans.lid[i] = a.lid[i], ans.rid[i] = b.rid[i];
  return ans;
}
int ls[M], rs[M], tsz, root;
void Build(int &c, int ss, int se) {
  c = ++tsz;
  if (ss == se) {
    int i, j;
    node[c].ss = node[c].se = ss;
    node[c].sol = node[c].nid = 0;
    for (i = 0; i < n; i = j) {
      for (j = i; j < n && mat[ss][j] == mat[ss][i]; j++)
        node[c].lid[j] = node[c].rid[j] = node[c].nid;
      node[c].nid++;
      node[c].sol++;
    }
    return;
  }
  int mid = ss + se >> 1;
  Build(ls[c], ss, mid);
  Build(rs[c], mid + 1, se);
  node[c] = Merge(node[ls[c]], node[rs[c]]);
}
Node Get(int c, int ss, int se, int qs, int qe) {
  if (qs <= ss && qe >= se) return node[c];
  int mid = ss + se >> 1;
  if (qe <= mid) return Get(ls[c], ss, mid, qs, qe);
  if (qs > mid) return Get(rs[c], mid + 1, se, qs, qe);
  return Merge(Get(ls[c], ss, mid, qs, qe), Get(rs[c], mid + 1, se, qs, qe));
}
int main() {
  int q, i, j, l, r;
  scanf("%i %i %i", &n, &m, &q);
  for (i = 0; i < n; i++)
    for (j = 1; j <= m; j++) scanf("%i", &mat[j][i]);
  Build(root, 1, m);
  while (q--) {
    scanf("%i %i", &l, &r);
    Node ans = Get(root, 1, m, l, r);
    printf("%i\n", ans.sol);
  }
  return 0;
}

```