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.util.Collection;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.InputStream;

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

  static class TaskE {
    int n;
    int k;
    int k2;
    int k4;
    int m;
    IntArrayList[] friends;
    IntervalTree iTree;
    DisjointSet dset;
    int[] newIdx;
    int[] newRight;

    public void solve(int testNumber, QuickScanner in, QuickWriter out) {
      n = in.nextInt();
      k = in.nextInt();
      k2 = k << 1;
      k4 = k << 2;
      m = in.nextInt();
      friends = new IntArrayList[n];
      for (int i = 0; i < n; ++i) {
        friends[i] = new IntArrayList();
      }
      for (int i = 0; i < m; ++i) {
        int u = in.nextInt() - 1;
        int v = in.nextInt() - 1;
        friends[Math.min(u, v)].add(Math.max(u, v));
      }
      dset = new DisjointSet(k4);
      newIdx = new int[k4];
      newRight = new int[k];
      iTree = new IntervalTree(n);
//System.out.println("!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!");
      for (int remQ = in.nextInt(); remQ > 0; --remQ) {
        int lower = in.nextInt() - 1;
        int upper = in.nextInt();
        out.println(iTree.calc(lower, upper));
      }
    }

    class IntervalTree extends AbstractSimpleIntervalTree {
      int cnt;
      int pnt;
      int[] lower;
      int[] size;
      int[] dsetCnt;
      int[][] left;
      int[][] right;

      public IntervalTree(int leafCapacity) {
        super(leafCapacity);
      }


      public void createSubclass(int nodeCapacity) {
        lower = new int[nodeCapacity];
        size = new int[nodeCapacity];
        dsetCnt = new int[nodeCapacity];
        left = new int[k][nodeCapacity];
        right = new int[k][nodeCapacity];
      }


      public void initLeaf(int nodeIdx, int idx) {
//System.out.printf("initLeaf(nodeIdx:%d idx:%d)\n", nodeIdx, idx);
        lower[nodeIdx] = idx;
        size[nodeIdx] = dsetCnt[nodeIdx] = 1;
        for (int i = 0; i < k; ++i) {
          left[i][nodeIdx] = -1;
          right[i][nodeIdx] = -1;
        }
        left[0][nodeIdx] = right[k - 1][nodeIdx] = 0;
      }


      public void merge(int nodeIdx, int leftNodeIdx, int rightNodeIdx) {
//System.out.printf("nodeIdx:%d leftNodeIdx:%d rightNodeIdx:%d\n", nodeIdx, leftNodeIdx, rightNodeIdx);
        copy(leftNodeIdx, nodeIdx);
        append(rightNodeIdx, nodeIdx);
//System.out.printf("nodeIdx(%d): lower(%d) size(%d) left(", nodeIdx, lower[nodeIdx], size[nodeIdx]);
//for (int i = 0; i < k; ++i) System.out.printf("%d,", left[i][nodeIdx]); System.out.print(") right(");
//for (int i = 0; i < k; ++i) System.out.printf("%d,", right[i][nodeIdx]); System.out.println();
      }


      public void calcAppend(int nodeIdx, int lower, int upper) {
        append(nodeIdx, 0);
      }

      public int calc(int lower, int upper) {
        size[0] = 0;
        calcRange(lower, upper);
        return dsetCnt[0];
      }

      void append(int fromIdx, int toIdx) {
        if (size[toIdx] == 0) {
          copy(fromIdx, toIdx);
          return;
        }
        dsetCnt[toIdx] += dsetCnt[fromIdx];
        dset.init(k4);
        for (int i = k - 1, x = lower[toIdx] + size[toIdx] - 1; i >= 0 && x >= lower[toIdx]; --i, --x)
          if (right[i][toIdx] >= 0) {
            for (int friendIdx = friends[x].size - 1; friendIdx >= 0; --friendIdx) {
              int y = friends[x].get(friendIdx);
              if (y < lower[fromIdx] || lower[fromIdx] + size[fromIdx] <= y) continue;
              int j = y - lower[fromIdx];
              if (left[j][fromIdx] >= 0 && !dset.isFriend(right[i][toIdx], k2 + left[j][fromIdx])) {
                --dsetCnt[toIdx];
                dset.setFriend(right[i][toIdx], k2 + left[j][fromIdx]);
              }
            }
          }
        size[toIdx] += size[fromIdx];
        Arrays.fill(newIdx, -1);
        cnt = 0;
        // left
        pnt = 0;
        updateLeft(toIdx, toIdx, 0);
        updateLeft(fromIdx, toIdx, k2);
        // right
        pnt = k - 1;
        Arrays.fill(newRight, -1);
        updateRight(fromIdx, k2);
        updateRight(toIdx, 0);
        for (int i = 0; i < k; ++i) {
          right[i][toIdx] = newRight[i];
        }
      }

      void copy(int fromIdx, int toIdx) {
        lower[toIdx] = lower[fromIdx];
        size[toIdx] = size[fromIdx];
        dsetCnt[toIdx] = dsetCnt[fromIdx];
        for (int i = 0; i < k; ++i) {
          left[i][toIdx] = left[i][fromIdx];
          right[i][toIdx] = right[i][fromIdx];
        }
      }

      void updateLeft(int fromIdx, int toIdx, int delta) {
        for (int i = 0; i < k && pnt < k; ++i)
          if (left[i][fromIdx] >= 0) {
            int root = dset.calcRoot(delta + left[i][fromIdx]);
            if (newIdx[root] == -1) {
              newIdx[root] = cnt++;
            }
            left[pnt++][toIdx] = newIdx[root];
          }
      }

      void updateRight(int fromIdx, int delta) {
        for (int i = k - 1; i >= 0 && pnt >= 0; --i)
          if (right[i][fromIdx] >= 0) {
            int root = dset.calcRoot(delta + right[i][fromIdx]);
            if (newIdx[root] == -1) {
              newIdx[root] = cnt++;
            }
            newRight[pnt--] = newIdx[root];
          }
      }

    }

  }

  static class QuickWriter {
    private final PrintWriter writer;

    public QuickWriter(OutputStream outputStream) {
      this.writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

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

    public void print(Object... objects) {
      for (int i = 0; i < objects.length; ++i) {
        if (i > 0) {
          writer.print(' ');
        }
        writer.print(objects[i]);
      }
    }

    public void println(Object... objects) {
      print(objects);
      writer.print('\n');
    }

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

  }

  static class IntArrayUtils {
    public static String toString(int[] values, int fromIdx, int toIdx) {
      StringBuilder sb = new StringBuilder("[");
      for (int i = fromIdx; i < toIdx; ++i) {
        if (i != fromIdx) sb.append(", ");
        sb.append(values[i]);
      }
      return sb.append("]").toString();
    }

  }

  static class IntArrayList implements IntCollection {
    private static final int[] EMPTY = {};
    public int[] values;
    public int size;

    public IntArrayList() {
      values = EMPTY;
      clear();
    }

    public IntArrayList(int capacity) {
      values = new int[IntUtils.nextPow2(capacity)];
      clear();
    }

    public IntArrayList(Collection<Integer> collection) {
      this(collection.size());
      addAll(collection);
    }


    public void clear() {
      size = 0;
    }


    public void add(int value) {
      ensureCapacity(size + 1);
      addInternal(value);
    }


    public void addAll(Collection<Integer> values) {
      ensureCapacity(size + values.size());
      for (int value : values) {
        addInternal(value);
      }
    }

    public int get(int idx) {
      if (idx >= size) throw new ArrayIndexOutOfBoundsException();
      return values[idx];
    }


    public String toString() {
      return IntArrayUtils.toString(values, 0, size);
    }

    public void ensureCapacity(int capacity) {
      if (capacity <= values.length) return;
      int[] newValues = new int[IntUtils.nextPow2(capacity)];
      for (int i = 0; i < size; ++i) {
        newValues[i] = values[i];
      }
      values = newValues;
    }

    private void addInternal(int value) {
      values[size++] = value;
    }

  }

  static class DisjointSet {
    public int[] parent;
    public int setCnt;

    public DisjointSet(int vertexCapacity) {
      this.parent = new int[vertexCapacity];
      init(vertexCapacity);
    }

    public void init(int n) {
      Arrays.fill(parent, 0, n, -1);
      setCnt = n;
    }

    public int calcRoot(int x) {
      int res = x;
      for (; parent[res] >= 0; res = parent[res]) {
      }
      shrink(x, res);
      return res;
    }

    public boolean isFriend(int x, int y) {
      return calcRoot(x) == calcRoot(y);
    }

    public void setFriend(int x, int y) {
      int rootX = calcRoot(x);
      int rootY = calcRoot(y);
      if (rootX != rootY) {
        parent[rootX] += parent[rootY];
        parent[rootY] = rootX;
        --setCnt;
      }
    }

    private void shrink(int x, int root) {
      while (parent[x] >= 0) {
        int y = parent[x];
        parent[x] = root;
        x = y;
      }
    }

  }

  static interface IntCollection {
  }

  static abstract class AbstractSimpleIntervalTree {
    private int n;
    private int[] lower;
    private int[] upper;
    private IntArrayList calcLeftIdx;
    private IntArrayList calcRightIdx;

    public abstract void createSubclass(int nodeCapacity);

    public abstract void initLeaf(int nodeIdx, int idx);

    public abstract void merge(int nodeIdx, int leftNodeIdx, int rightNodeIdx);

    public abstract void calcAppend(int nodeIdx, int lower, int upper);

    public AbstractSimpleIntervalTree(int leafCapacity) {
      calcLeftIdx = new IntArrayList();
      calcRightIdx = new IntArrayList();
      int leafCapacity2 = leafCapacity << 1;
      lower = new int[leafCapacity2];
      upper = new int[leafCapacity2];
      createSubclass(leafCapacity2);
      init(leafCapacity);
    }

    public void init(int n) {
      this.n = n;
      for (int i = 0; i < n; ++i) {
        lower[n + i] = i;
        upper[n + i] = i + 1;
        initLeaf(n + i, i);
      }
      for (int i = n - 1; i > 0; --i) {
        int left = i << 1, right = left | 1;
        if (upper[left] == lower[right]) {
          lower[i] = lower[left];
          upper[i] = upper[right];
          merge(i, left, right);
        } else {
          lower[i] = -1;
        }
      }
    }

    public void calcRange(int lower, int upper) {
      calcLeftIdx.clear();
      calcRightIdx.clear();
      for (lower += n, upper += n; lower < upper; lower >>= 1, upper >>= 1) {
        if ((lower & 1) > 0) calcLeftIdx.add(lower++);
        if ((upper & 1) > 0) calcRightIdx.add(--upper);
      }
      for (int i = 0; i < calcLeftIdx.size; ++i) {
        int idx = calcLeftIdx.get(i);
        calcAppend(idx, this.lower[idx], this.upper[idx]);
      }
      for (int i = calcRightIdx.size - 1; i >= 0; --i) {
        int idx = calcRightIdx.get(i);
        calcAppend(idx, this.lower[idx], this.upper[idx]);
      }
    }

  }

  static class IntUtils {
    public static boolean isPow2(int n) {
      return n > 0 && (n & (n - 1)) == 0;
    }

    public static int nextPow2(int n) {
      if (n < 1) return 1;
      return isPow2(n) ? n : Integer.highestOneBit(n) << 1;
    }

  }

  static class QuickScanner {
    private static final int BUFFER_SIZE = 1024;
    private InputStream stream;
    private byte[] buffer;
    private int currentPosition;
    private int numberOfChars;

    public QuickScanner(InputStream stream) {
      this.stream = stream;
      this.buffer = new byte[BUFFER_SIZE];
      this.currentPosition = 0;
      this.numberOfChars = 0;
    }

    public int nextInt() {
      int c = nextNonSpaceChar();
      boolean positive = true;
      if (c == '-') {
        positive = false;
        c = nextChar();
      }
      int res = 0;
      do {
        if (c < '0' || '9' < c) throw new RuntimeException();
        res = res * 10 + c - '0';
        c = nextChar();
      } while (!isSpaceChar(c));
      return positive ? res : -res;
    }

    public int nextNonSpaceChar() {
      int res = nextChar();
      for (; isSpaceChar(res) || res < 0; res = nextChar()) ;
      return res;
    }

    public int nextChar() {
      if (numberOfChars == -1) {
        throw new RuntimeException();
      }
      if (currentPosition >= numberOfChars) {
        currentPosition = 0;
        try {
          numberOfChars = stream.read(buffer);
        } catch (Exception e) {
          throw new RuntimeException(e);
        }
        if (numberOfChars <= 0) {
          return -1;
        }
      }
      return buffer[currentPosition++];
    }

    public boolean isSpaceChar(int c) {
      return c == ' ' || c == '\t' || isEndOfLineChar(c);
    }

    public boolean isEndOfLineChar(int c) {
      return c == '\n' || c == '\r' || c < 0;
    }

  }
}

