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>
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author niquefa_diego
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE {
        int h;
        int[][] mat;

        Data merge(Data L, Data R) {
            assert (L.to + 1 == R.fr);
            Data ans = new Data(L.fr, R.to);
            ans.colors = L.colors + R.colors;

            int[] Lr = Arrays.copyOf(L.r, h);
            int[] Rl = Arrays.copyOf(R.l, h);
            for (int i = 0; i < h; ++i) {
                ans.l[i] = L.l[i];
                ans.r[i] = L.size() + R.r[i];
                Rl[i] += L.size();
            }

            for (int i = 0; i < h; ++i)
                if (mat[i][L.to] == mat[i][R.fr]) {
                    int oldC = Rl[i];
                    int newC = Lr[i];
                    ans.mergeColors(oldC, newC, Rl, Lr);
                }
            return ans;
        }

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            h = in.nextInt();
            int w = in.nextInt();
            int nQueries = in.nextInt();

            mat = new int[h][w];
            for (int i = 0; i < h; ++i)
                for (int j = 0; j < w; ++j)
                    mat[i][j] = in.nextInt();

            Node stree = new Node(0, w - 1);
            while (nQueries-- > 0) {
                int l = in.nextInt() - 1;
                int r = in.nextInt() - 1;
                out.println(stree.query(l, r).colors);
            }

        }

        class Data {
            int[] l;
            int[] r;
            int colors;
            int fr;
            int to;

            int size() {
                return h * (to - fr + 1);
            }

            public String toString() {
                return "Data [" + fr + "," + to + "] colors=" + colors + "\n   l=" + Arrays.toString(l)
                        + "\n   r=" + Arrays.toString(r);
            }

            void mergeColors(int oldColor, int newColor, int[] Lr, int[] Rl) {
                if (oldColor == newColor)
                    return;
                boolean flag = false;
                for (int i = 0; i < h; ++i) {
                    if (l[i] == oldColor) {
                        l[i] = newColor;
                        flag = true;
                    }
                    if (r[i] == oldColor) {
                        r[i] = newColor;
                        flag = true;
                    }
                    if (Rl[i] == oldColor) {
                        Rl[i] = newColor;
                        flag = true;
                    }
                    if (Lr[i] == oldColor) {
                        Lr[i] = newColor;
                        flag = true;
                    }
                }
                if (flag) colors--;
            }

            Data(int fr, int to) {
                this.fr = fr;
                this.to = to;
                l = new int[h];
                r = new int[h];
            }

        }

        class Node {
            Node L;
            Node R;
            Data data;

            Data query(int fr, int to) {
                if (data.fr == fr && data.to == to) return data;
                if (to <= L.data.to) return L.query(fr, to);
                if (fr >= R.data.fr) return R.query(fr, to);
                return merge(L.query(fr, L.data.to), R.query(R.data.fr, to));
            }

            Node(int fr, int to) {
                data = new Data(fr, to);
                if (fr == to) {
                    for (int i = 0; i < h; ++i) {
                        if (i > 0 && mat[i][fr] == mat[i - 1][fr])
                            data.l[i] = data.l[i - 1];
                        else data.l[i] = data.colors++;
                        data.r[i] = data.l[i];
                    }
                } else {
                    L = new Node(fr, (fr + to) / 2);
                    R = new Node((fr + to) / 2 + 1, to);
                    data = merge(L.data, R.data);
                }
            }

        }

    }

    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer = null;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}

