After his birthday party, Timofey went to his favorite tree alley in a park. He wants to feed there his favorite birds — crows.

It's widely known that each tree is occupied by a single crow family. The trees in the alley form a row and are numbered from 1 to n. Some families are friends to each other. For some reasons, two families can be friends only if they live not too far from each other, more precisely, there is no more than k - 1 trees between any pair of friend families. Formally, the family on the u-th tree and the family on the v-th tree can be friends only if |u - v| ≤ k holds.

One of the friendship features is that if some family learns that Timofey is feeding crows somewhere, it notifies about this all friend families. Thus, after Timofey starts to feed crows under some tree, all the families that are friends to the family living on this tree, as well as their friends and so on, fly to the feeding place. Of course, the family living on the tree also comes to the feeding place.

Today Timofey came to the alley and noticed that all the families that live on trees with numbers strictly less than l or strictly greater than r have flown away. Thus, it is not possible to pass the information about feeding through them. Moreover, there is no need to feed them. Help Timofey to learn what is the minimum number of trees under which he has to feed crows so that all the families that have remained will get the information about feeding. You are given several situations, described by integers l and r, you need to calculate the answer for all of them.

Input

The first line contains integers n and k (1 ≤ n ≤ 105, 1 ≤ k ≤ 5), where n is the number of trees, and k is the maximum possible distance between friend families.

The next line contains single integer m (0 ≤ m ≤ n·k) — the number of pair of friend families. 

Each of the next m lines contains two integers u and v (1 ≤ u, v ≤ 105), that means that the families on trees u and v are friends. It is guaranteed that u ≠ v and |u - v| ≤ k. All the given pairs are distinct.

The next line contains single integer q (1 ≤ q ≤ 105) — the number of situations you need to calculate the answer in.

Each of the next q lines contains two integers l and r (1 ≤ l ≤ r ≤ 105), that means that in this situation families that have flown away lived on such trees x, so that either x < l or x > r.

Output

Print q lines. Line i should contain single integer — the answer in the i-th situation.

Example

Input

5 3
3
1 3
2 3
4 5
5
1 1
1 2
2 3
1 3
1 5


Output

1
2
1
1
2

Note

In the first example the following family pairs are friends: (1, 3), (2, 3) and (4, 5).

  * In the first situation only the first family has remained, so the answer is 1. 
  * In the second situation the first two families have remained, and they aren't friends, so the answer is 2. 
  * In the third situation the families 2 and 3 are friends, so it is enough to feed any of them, the answer is 1. 
  * In the fourth situation we can feed the first family, then the third family will get the information from the first family, and the second family will get the information from the third. The answer is 1. 
  * In the fifth situation we can feed the first and the fifth families, so the answer is 2. 
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.util.InputMismatchException;
import java.io.IOException;
import java.util.Random;
import java.io.InputStream;

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

    static class TaskE {
        int n;
        int k;
        Graph graph;
        RecursiveIndependentSetSystem[] independentSetSystems;
        int[] treeCntTree;
        int answer;
        int cntSub;
        int[] parent;
        Random rnd = new Random(228);

        int getParent(int v) {
            if (parent[v] == v) {
                return v;
            }
            return parent[v] = getParent(parent[v]);
        }

        private boolean unit(int i, int j) {
            if (rnd.nextBoolean()) {
                return unit(j, i);
            }

            i = getParent(i);
            j = getParent(j);
            if (parent[i] == parent[j]) {
                return false;
            }
            parent[i] = j;
            return true;
        }

        private void getAns(int level, int v, int tl, int tr, int l, int r) {
            if (r < tl || tr < l) {
                return;
            }

            RecursiveIndependentSetSystem iss = independentSetSystems[level];
            if (l <= tl && tr <= r) {
                answer += treeCntTree[v];
                int leftRange = Math.min(tl + k - 1, tr);
                for (int pos = tl; pos <= leftRange; pos++) {
                    int leader = iss.get(pos);
                    parent[pos] = leader;
                    parent[leader] = leader;
                }
                for (int pos = Math.max(leftRange + 1, Math.max(tr - (k - 1), tl)); pos <= tr; pos++) {
                    int leader = iss.get(pos);
                    parent[pos] = leader;
                    parent[leader] = leader;
                }

                for (int pos = tl; pos <= leftRange; pos++) {
                    for (int id = graph.firstOutbound(pos); id != -1; id = graph.nextOutbound(id)) {
                        int to = graph.destination(id);
                        if (l <= to && to < tl) {
                            if (unit(pos, to)) {
                                ++cntSub;
                            }
                        }
                    }
                }
            } else {
                int tm = (tl + tr) >>> 1;
                getAns(level + 1, v + v + 1, tl, tm, l, r);
                getAns(level + 1, v + v + 2, tm + 1, tr, l, r);
            }
        }

        private void init(int level, int v, int tl, int tr) {
            if (independentSetSystems[level] == null) {
                independentSetSystems[level] = new RecursiveIndependentSetSystem(n);
            }
            RecursiveIndependentSetSystem iss = independentSetSystems[level];

            if (tl == tr) {
            } else {
                int tm = (tl + tr) >>> 1;
                init(level + 1, v + v + 1, tl, tm);
                init(level + 1, v + v + 2, tm + 1, tr);
            }

            treeCntTree[v] = tr - tl + 1;
            for (int pos = tl; pos <= tr; pos++) {
                for (int id = graph.firstOutbound(pos); id != -1; id = graph.nextOutbound(id)) {
                    int to = graph.destination(id);
                    if (tl <= to && to <= tr) {
                        if (iss.join(pos, to)) {
                            --treeCntTree[v];
                        }
                    }
                }
            }
        }

        public void solve(int testNumber, InputReader in, OutputWriter out) {
            n = in.readInt();
            k = in.readInt();
            int m = in.readInt();
            graph = new Graph(n, m);
            for (int iter = 0; iter < m; iter++) {
                int a = in.readInt() - 1;
                int b = in.readInt() - 1;
                graph.addSimpleEdge(Math.max(a, b), Math.min(a, b));
            }

            independentSetSystems = new RecursiveIndependentSetSystem[100];
            treeCntTree = new int[4 * n];
            init(0, 0, 0, n - 1);


            int q = in.readInt();
            parent = new int[n];
            for (int iter = 0; iter < q; iter++) {
                int l = in.readInt() - 1;
                int r = in.readInt() - 1;

                answer = 0;
                cntSub = 0;
//            Arrays.fill(parent, -1);
                getAns(0, 0, 0, n - 1, l, r);
                out.printLine(answer - cntSub);
            }
        }

    }

    static interface Edge {
    }

    static class RecursiveIndependentSetSystem implements IndependentSetSystem {
        private final int[] color;
        public final int[] rank;
        private int setCount;
        private IndependentSetSystem.Listener listener;

        public RecursiveIndependentSetSystem(int size) {
            color = new int[size];
            rank = new int[size];
            for (int i = 0; i < size; i++) {
                color[i] = i;
            }
            setCount = size;
        }

        public RecursiveIndependentSetSystem(RecursiveIndependentSetSystem other) {
            color = other.color.clone();
            rank = other.rank.clone();
            setCount = other.setCount;
        }

        public boolean join(int first, int second) {
            first = get(first);
            second = get(second);
            if (first == second) {
                return false;
            }
            if (rank[first] < rank[second]) {
                int temp = first;
                first = second;
                second = temp;
            } else if (rank[first] == rank[second]) {
                rank[first]++;
            }
            setCount--;
            color[second] = first;
            if (listener != null) {
                listener.joined(second, first);
            }
            return true;
        }

        public int get(int index) {
            int start = index;
            while (color[index] != index) {
                index = color[index];
            }
            while (start != index) {
                int next = color[start];
                color[start] = index;
                start = next;
            }
            return index;
        }

    }

    static class InputReader {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private InputReader.SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int read() {
            if (numChars == -1) {
                throw new InputMismatchException();
            }
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0) {
                    return -1;
                }
            }
            return buf[curChar++];
        }

        public int readInt() {
            int c = read();
            while (isSpaceChar(c)) {
                c = read();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if ((c < '0') || (c > '9')) {
                    throw new InputMismatchException();
                }
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public boolean isSpaceChar(int c) {
            if (filter != null) {
                return filter.isSpaceChar(c);
            }
            return isWhitespace(c);
        }

        public static boolean isWhitespace(int c) {
            return (c == ' ') || (c == '\n') || (c == '\r') || (c == '\t') || (c == -1);
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);

        }

    }

    static interface IndependentSetSystem {
        public static interface Listener {
            public void joined(int joinedRoot, int root);

        }

    }

    static class Graph {
        public static final int REMOVED_BIT = 0;
        protected int vertexCount;
        protected int edgeCount;
        private int[] firstOutbound;
        private int[] firstInbound;
        private Edge[] edges;
        private int[] nextInbound;
        private int[] nextOutbound;
        private int[] from;
        private int[] to;
        public long[] weight;
        public long[] capacity;
        private int[] reverseEdge;
        private int[] flags;

        public Graph(int vertexCount) {
            this(vertexCount, vertexCount);
        }

        public Graph(int vertexCount, int edgeCapacity) {
            this.vertexCount = vertexCount;
            firstOutbound = new int[vertexCount];
            Arrays.fill(firstOutbound, -1);

            from = new int[edgeCapacity];
            to = new int[edgeCapacity];
            nextOutbound = new int[edgeCapacity];
            flags = new int[edgeCapacity];
        }

        public int addEdge(int fromID, int toID, long weight, long capacity, int reverseEdge) {
            ensureEdgeCapacity(edgeCount + 1);
            if (firstOutbound[fromID] != -1) {
                nextOutbound[edgeCount] = firstOutbound[fromID];
            } else {
                nextOutbound[edgeCount] = -1;
            }
            firstOutbound[fromID] = edgeCount;
            if (firstInbound != null) {
                if (firstInbound[toID] != -1) {
                    nextInbound[edgeCount] = firstInbound[toID];
                } else {
                    nextInbound[edgeCount] = -1;
                }
                firstInbound[toID] = edgeCount;
            }
            this.from[edgeCount] = fromID;
            this.to[edgeCount] = toID;
            if (capacity != 0) {
                if (this.capacity == null) {
                    this.capacity = new long[from.length];
                }
                this.capacity[edgeCount] = capacity;
            }
            if (weight != 0) {
                if (this.weight == null) {
                    this.weight = new long[from.length];
                }
                this.weight[edgeCount] = weight;
            }
            if (reverseEdge != -1) {
                if (this.reverseEdge == null) {
                    this.reverseEdge = new int[from.length];
                    Arrays.fill(this.reverseEdge, 0, edgeCount, -1);
                }
                this.reverseEdge[edgeCount] = reverseEdge;
            }
            if (edges != null) {
                edges[edgeCount] = createEdge(edgeCount);
            }
            return edgeCount++;
        }

        protected final GraphEdge createEdge(int id) {
            return new GraphEdge(id);
        }

        public final int addFlowWeightedEdge(int from, int to, long weight, long capacity) {
            if (capacity == 0) {
                return addEdge(from, to, weight, 0, -1);
            } else {
                int lastEdgeCount = edgeCount;
                addEdge(to, from, -weight, 0, lastEdgeCount + entriesPerEdge());
                return addEdge(from, to, weight, capacity, lastEdgeCount);
            }
        }

        protected int entriesPerEdge() {
            return 1;
        }

        public final int addWeightedEdge(int from, int to, long weight) {
            return addFlowWeightedEdge(from, to, weight, 0);
        }

        public final int addSimpleEdge(int from, int to) {
            return addWeightedEdge(from, to, 0);
        }

        public final int firstOutbound(int vertex) {
            int id = firstOutbound[vertex];
            while ((id != -1) && isRemoved(id)) {
                id = nextOutbound[id];
            }
            return id;
        }

        public final int nextOutbound(int id) {
            id = nextOutbound[id];
            while ((id != -1) && isRemoved(id)) {
                id = nextOutbound[id];
            }
            return id;
        }

        public final int destination(int id) {
            return to[id];
        }

        public final boolean flag(int id, int bit) {
            return ((flags[id] >> bit) & 1) != 0;
        }

        public final boolean isRemoved(int id) {
            return flag(id, REMOVED_BIT);
        }

        protected void ensureEdgeCapacity(int size) {
            if (from.length < size) {
                int newSize = Math.max(size, 2 * from.length);
                if (edges != null) {
                    edges = resize(edges, newSize);
                }
                from = resize(from, newSize);
                to = resize(to, newSize);
                nextOutbound = resize(nextOutbound, newSize);
                if (nextInbound != null) {
                    nextInbound = resize(nextInbound, newSize);
                }
                if (weight != null) {
                    weight = resize(weight, newSize);
                }
                if (capacity != null) {
                    capacity = resize(capacity, newSize);
                }
                if (reverseEdge != null) {
                    reverseEdge = resize(reverseEdge, newSize);
                }
                flags = resize(flags, newSize);
            }
        }

        protected final int[] resize(int[] array, int size) {
            int[] newArray = new int[size];
            System.arraycopy(array, 0, newArray, 0, array.length);
            return newArray;
        }

        private long[] resize(long[] array, int size) {
            long[] newArray = new long[size];
            System.arraycopy(array, 0, newArray, 0, array.length);
            return newArray;
        }

        private Edge[] resize(Edge[] array, int size) {
            Edge[] newArray = new Edge[size];
            System.arraycopy(array, 0, newArray, 0, array.length);
            return newArray;
        }

        protected class GraphEdge implements Edge {
            protected int id;

            protected GraphEdge(int id) {
                this.id = id;
            }

        }

    }

    static class OutputWriter {
        private final PrintWriter writer;

        public OutputWriter(OutputStream outputStream) {
            writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        public OutputWriter(Writer writer) {
            this.writer = new PrintWriter(writer);
        }

        public void close() {
            writer.close();
        }

        public void printLine(int i) {
            writer.println(i);
        }

    }
}

