#include <bits/stdc++.h>
using namespace std;
inline int read() {
  int sum = 0;
  char c = getchar();
  bool f = 0;
  while (c < '0' || c > '9') {
    if (c == '-') f = 1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    sum = sum * 10 + c - '0';
    c = getchar();
  }
  if (f) return -sum;
  return sum;
}
const int N = 100005;
int n, m, q, p, z, col[11][N];
struct node {
  int lc[11], rc[11], s, l, r;
} t[N * 4];
int f[50], g[50];
inline int find(int x) {
  if (f[x] == x) return x;
  f[x] = find(f[x]);
  return f[x];
}
inline node merge(const node &a, const node &b) {
  int i, j, x, y;
  node c;
  c.s = a.s + b.s;
  c.l = a.l;
  c.r = b.r;
  j = a.r;
  for (i = 1; i <= p; i++) f[i] = i, g[i] = 0;
  for (i = 1; i <= n; i++)
    if (col[i][j] == col[i][j + 1]) {
      x = find(a.rc[i]);
      y = find(z + b.lc[i]);
      if (x == y) continue;
      f[x] = y;
      c.s--;
    }
  for (i = 1; i <= n; i++) g[find(a.lc[i])] = 1, g[find(z + b.rc[i])] = 1;
  for (i = 1; i <= p; i++) g[i] += g[i - 1];
  for (i = 1; i <= n; i++)
    c.lc[i] = g[find(a.lc[i])], c.rc[i] = g[find(z + b.rc[i])];
  return c;
}
inline void into(node &p, int x) {
  p.s = n;
  p.l = p.r = x;
  int i, tot = 0;
  for (i = 1; i <= n; i++)
    if (col[i - 1][x] == col[i][x])
      p.s--, p.lc[i] = p.rc[i] = p.lc[i - 1];
    else
      p.lc[i] = p.rc[i] = ++tot;
}
inline void build(int p, int l, int r) {
  if (l == r) {
    into(t[p], l);
    return;
  }
  int mid = (l + r) >> 1;
  build(p << 1, l, mid);
  build(p << 1 | 1, mid + 1, r);
  t[p] = merge(t[p << 1], t[p << 1 | 1]);
}
inline node ask(int p, int l, int r, int L, int R) {
  if (l == L && r == R) return t[p];
  int mid = (l + r) >> 1;
  if (R <= mid)
    return ask(p << 1, l, mid, L, R);
  else if (L > mid)
    return ask(p << 1 | 1, mid + 1, r, L, R);
  else
    return merge(ask(p << 1, l, mid, L, mid),
                 ask(p << 1 | 1, mid + 1, r, mid + 1, R));
}
int main() {
  int i, j, l, r;
  n = read();
  m = read();
  q = read();
  p = n * 4;
  z = n * 2;
  for (i = 1; i <= n; i++)
    for (j = 1; j <= m; j++) col[i][j] = read();
  build(1, 1, m);
  while (q--) {
    l = read();
    r = read();
    printf("%d\n", ask(1, 1, m, l, r).s);
  }
  return 0;
}

### 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;
inline int read() {
  int sum = 0;
  char c = getchar();
  bool f = 0;
  while (c < '0' || c > '9') {
    if (c == '-') f = 1;
    c = getchar();
  }
  while (c >= '0' && c <= '9') {
    sum = sum * 10 + c - '0';
    c = getchar();
  }
  if (f) return -sum;
  return sum;
}
const int N = 100005;
int n, m, q, p, z, col[11][N];
struct node {
  int lc[11], rc[11], s, l, r;
} t[N * 4];
int f[50], g[50];
inline int find(int x) {
  if (f[x] == x) return x;
  f[x] = find(f[x]);
  return f[x];
}
inline node merge(const node &a, const node &b) {
  int i, j, x, y;
  node c;
  c.s = a.s + b.s;
  c.l = a.l;
  c.r = b.r;
  j = a.r;
  for (i = 1; i <= p; i++) f[i] = i, g[i] = 0;
  for (i = 1; i <= n; i++)
    if (col[i][j] == col[i][j + 1]) {
      x = find(a.rc[i]);
      y = find(z + b.lc[i]);
      if (x == y) continue;
      f[x] = y;
      c.s--;
    }
  for (i = 1; i <= n; i++) g[find(a.lc[i])] = 1, g[find(z + b.rc[i])] = 1;
  for (i = 1; i <= p; i++) g[i] += g[i - 1];
  for (i = 1; i <= n; i++)
    c.lc[i] = g[find(a.lc[i])], c.rc[i] = g[find(z + b.rc[i])];
  return c;
}
inline void into(node &p, int x) {
  p.s = n;
  p.l = p.r = x;
  int i, tot = 0;
  for (i = 1; i <= n; i++)
    if (col[i - 1][x] == col[i][x])
      p.s--, p.lc[i] = p.rc[i] = p.lc[i - 1];
    else
      p.lc[i] = p.rc[i] = ++tot;
}
inline void build(int p, int l, int r) {
  if (l == r) {
    into(t[p], l);
    return;
  }
  int mid = (l + r) >> 1;
  build(p << 1, l, mid);
  build(p << 1 | 1, mid + 1, r);
  t[p] = merge(t[p << 1], t[p << 1 | 1]);
}
inline node ask(int p, int l, int r, int L, int R) {
  if (l == L && r == R) return t[p];
  int mid = (l + r) >> 1;
  if (R <= mid)
    return ask(p << 1, l, mid, L, R);
  else if (L > mid)
    return ask(p << 1 | 1, mid + 1, r, L, R);
  else
    return merge(ask(p << 1, l, mid, L, mid),
                 ask(p << 1 | 1, mid + 1, r, mid + 1, R));
}
int main() {
  int i, j, l, r;
  n = read();
  m = read();
  q = read();
  p = n * 4;
  z = n * 2;
  for (i = 1; i <= n; i++)
    for (j = 1; j <= m; j++) col[i][j] = read();
  build(1, 1, m);
  while (q--) {
    l = read();
    r = read();
    printf("%d\n", ask(1, 1, m, l, r).s);
  }
  return 0;
}

```