#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
const long long INF = 1e15 + 1;
int a[10][N];
int n, m, q;
struct NODE {
  int num;
  pair<int, int> front[10], back[10];
  void change(int x, int y) {
    num--;
    for (int i = 0; i < n; i++) {
      if (front[i].second == x) front[i].second = y;
      if (back[i].second == x) back[i].second = y;
    }
  }
} t[N * 8];
NODE merge(NODE a, NODE b) {
  NODE res;
  res.num = a.num + b.num;
  for (int i = 0; i < n; i++) {
    res.front[i] = a.front[i];
    res.back[i] = b.back[i];
  }
  for (int i = 0; i < n; i++) {
    if (a.back[i].first == b.front[i].first &&
        a.back[i].second != b.front[i].second) {
      pair<int, int> tmp = make_pair(a.back[i].second, b.front[i].second);
      a.change(tmp.first, tmp.second);
      res.change(tmp.first, tmp.second);
    }
  }
  return res;
}
void BuildTree(int cur, int l, int r) {
  if (l == r) {
    for (int i = 0; i < n; i++) {
      if (i != 0 && a[i][l] == a[i - 1][l]) {
        t[cur].front[i] = t[cur].back[i] = t[cur].front[i - 1];
      } else {
        t[cur].front[i] = t[cur].back[i] = make_pair(a[i][l], l * 10 + i);
        t[cur].num++;
      }
    }
  } else {
    int m = (l + r) / 2;
    int next_cur = cur * 2;
    BuildTree(next_cur, l, m);
    BuildTree(next_cur + 1, m + 1, r);
    t[cur] = merge(t[next_cur], t[next_cur + 1]);
  }
}
NODE get_ans(int cur, int l, int r, int L, int R) {
  if (l == L && r == R)
    return t[cur];
  else {
    int m = (l + r) / 2;
    int next_cur = cur * 2;
    if (R <= m) {
      return get_ans(next_cur, l, m, L, R);
    } else if (L >= m + 1) {
      return get_ans(next_cur + 1, m + 1, r, L, R);
    } else {
      return merge(get_ans(next_cur, l, m, L, m),
                   get_ans(next_cur + 1, m + 1, r, m + 1, R));
    }
  }
}
int main() {
  scanf("%d%d%d", &n, &m, &q);
  for (int i = 0; i < n; i++)
    for (int j = 1; j <= m; j++) scanf("%d", &a[i][j]);
  BuildTree(1, 1, m);
  while (q-- > 0) {
    int l, r;
    scanf("%d%d", &l, &r);
    NODE ans = get_ans(1, 1, m, l, r);
    printf("%d\n", ans.num);
  }
  return 0;
}

### Prompt

Your task is to create 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;
const int N = 100010;
const long long INF = 1e15 + 1;
int a[10][N];
int n, m, q;
struct NODE {
  int num;
  pair<int, int> front[10], back[10];
  void change(int x, int y) {
    num--;
    for (int i = 0; i < n; i++) {
      if (front[i].second == x) front[i].second = y;
      if (back[i].second == x) back[i].second = y;
    }
  }
} t[N * 8];
NODE merge(NODE a, NODE b) {
  NODE res;
  res.num = a.num + b.num;
  for (int i = 0; i < n; i++) {
    res.front[i] = a.front[i];
    res.back[i] = b.back[i];
  }
  for (int i = 0; i < n; i++) {
    if (a.back[i].first == b.front[i].first &&
        a.back[i].second != b.front[i].second) {
      pair<int, int> tmp = make_pair(a.back[i].second, b.front[i].second);
      a.change(tmp.first, tmp.second);
      res.change(tmp.first, tmp.second);
    }
  }
  return res;
}
void BuildTree(int cur, int l, int r) {
  if (l == r) {
    for (int i = 0; i < n; i++) {
      if (i != 0 && a[i][l] == a[i - 1][l]) {
        t[cur].front[i] = t[cur].back[i] = t[cur].front[i - 1];
      } else {
        t[cur].front[i] = t[cur].back[i] = make_pair(a[i][l], l * 10 + i);
        t[cur].num++;
      }
    }
  } else {
    int m = (l + r) / 2;
    int next_cur = cur * 2;
    BuildTree(next_cur, l, m);
    BuildTree(next_cur + 1, m + 1, r);
    t[cur] = merge(t[next_cur], t[next_cur + 1]);
  }
}
NODE get_ans(int cur, int l, int r, int L, int R) {
  if (l == L && r == R)
    return t[cur];
  else {
    int m = (l + r) / 2;
    int next_cur = cur * 2;
    if (R <= m) {
      return get_ans(next_cur, l, m, L, R);
    } else if (L >= m + 1) {
      return get_ans(next_cur + 1, m + 1, r, L, R);
    } else {
      return merge(get_ans(next_cur, l, m, L, m),
                   get_ans(next_cur + 1, m + 1, r, m + 1, R));
    }
  }
}
int main() {
  scanf("%d%d%d", &n, &m, &q);
  for (int i = 0; i < n; i++)
    for (int j = 1; j <= m; j++) scanf("%d", &a[i][j]);
  BuildTree(1, 1, m);
  while (q-- > 0) {
    int l, r;
    scanf("%d%d", &l, &r);
    NODE ans = get_ans(1, 1, m, l, r);
    printf("%d\n", ans.num);
  }
  return 0;
}

```