Mr. Kitayuta has just bought an undirected graph with n vertices and m edges. The vertices of the graph are numbered from 1 to n. Each edge, namely edge i, has a color ci, connecting vertex ai and bi.

Mr. Kitayuta wants you to process the following q queries.

In the i-th query, he gives you two integers - ui and vi.

Find the number of the colors that satisfy the following condition: the edges of that color connect vertex ui and vertex vi directly or indirectly.

Input

The first line of the input contains space-separated two integers - n and m(2 ≤ n ≤ 105, 1 ≤ m ≤ 105), denoting the number of the vertices and the number of the edges, respectively.

The next m lines contain space-separated three integers - ai, bi(1 ≤ ai < bi ≤ n) and ci(1 ≤ ci ≤ m). Note that there can be multiple edges between two vertices. However, there are no multiple edges of the same color between two vertices, that is, if i ≠ j, (ai, bi, ci) ≠ (aj, bj, cj).

The next line contains a integer- q(1 ≤ q ≤ 105), denoting the number of the queries.

Then follows q lines, containing space-separated two integers - ui and vi(1 ≤ ui, vi ≤ n). It is guaranteed that ui ≠ vi.

Output

For each query, print the answer in a separate line.

Examples

Input

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


Output

2
1
0


Input

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


Output

1
1
1
1
2

Note

Let's consider the first sample. 

<image> The figure above shows the first sample. 

  * Vertex 1 and vertex 2 are connected by color 1 and 2. 
  * Vertex 3 and vertex 4 are connected by color 3. 
  * Vertex 1 and vertex 4 are not connected by any single color. 
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class _505E {

  @SuppressWarnings("unchecked")
  public static void main(String[] args) throws Exception {
    Reader.init(System.in);
    BufferedWriter cout = new BufferedWriter(new OutputStreamWriter(System.out));

    int n = Reader.nextInt();
    int m = Reader.nextInt();
    boolean[][][] a = new boolean[100][n][n];
    for (int i = 0; i < m; i++) {
      int u = Reader.nextInt() - 1;
      int v = Reader.nextInt() - 1;
      int color = Reader.nextInt() - 1;
      a[color][u][v] = a[color][v][u] = true;
    }

    for (int color = 0; color < 100; color++)
      for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
          for (int j = 0; j < n; j++)
            a[color][i][j] = a[color][i][j] || (a[color][i][k] && a[color][k][j]);

    for (int q = Reader.nextInt(); q > 0; q--) {
      int u = Reader.nextInt() - 1;
      int v = Reader.nextInt() - 1;
      int ans = 0;
      for (int i = 0; i < a.length; i++)
        if (a[i][u][v])
          ans++;
      System.out.println(ans);
    }

    cout.close();
  }

  static class Pair<U extends Comparable<U>, V extends Comparable<V>> implements Comparable<Pair<U, V>> {
    final U _1;
    final V _2;

    private Pair(U key, V val) {
      this._1 = key;
      this._2 = val;
    }

    public static <U extends Comparable<U>, V extends Comparable<V>> Pair<U, V> instanceOf(U _1, V _2) {
      return new Pair<U, V>(_1, _2);
    }

    @Override
    public String toString() {
      return _1 + " " + _2;
    }

    @Override
    public int hashCode() {
      int res = 17;
      res = res * 31 + _1.hashCode();
      res = res * 31 + _2.hashCode();
      return res;
    }

    @Override
    public int compareTo(Pair<U, V> that) {
      int res = this._1.compareTo(that._1);
      if (res < 0 || res > 0)
        return res;
      else
        return this._2.compareTo(that._2);
    }

    @Override
    public boolean equals(Object obj) {
      if (this == obj)
        return true;
      if (!(obj instanceof Pair))
        return false;
      Pair<?, ?> that = (Pair<?, ?>) obj;
      return _1.equals(that._1) && _2.equals(that._2);
    }
  }

  /** Class for buffered reading int and double values */
  static class Reader {
    static BufferedReader reader;
    static StringTokenizer tokenizer;

    /** call this method to initialize reader for InputStream */
    static void init(InputStream input) {
      reader = new BufferedReader(new InputStreamReader(input));
      tokenizer = new StringTokenizer("");
    }

    /** get next word */
    static String next() throws IOException {
      while (!tokenizer.hasMoreTokens()) {
        // TODO add check for eof if necessary
        tokenizer = new StringTokenizer(reader.readLine());
      }
      return tokenizer.nextToken();
    }

    static int nextInt() throws IOException {
      return Integer.parseInt(next());
    }

    static double nextDouble() throws IOException {
      return Double.parseDouble(next());
    }
  }

  static class ArrayUtil {
    static void swap(int[] a, int i, int j) {
      int tmp = a[i];
      a[i] = a[j];
      a[j] = tmp;
    }

    static void swap(long[] a, int i, int j) {
      long tmp = a[i];
      a[i] = a[j];
      a[j] = tmp;
    }

    static void swap(double[] a, int i, int j) {
      double tmp = a[i];
      a[i] = a[j];
      a[j] = tmp;
    }

    static void swap(char[] a, int i, int j) {
      char tmp = a[i];
      a[i] = a[j];
      a[j] = tmp;
    }

    static void swap(boolean[] a, int i, int j) {
      boolean tmp = a[i];
      a[i] = a[j];
      a[j] = tmp;
    }

    static void reverse(int[] a, int i, int j) {
      for (; i < j; i++, j--)
        swap(a, i, j);
    }

    static void reverse(long[] a, int i, int j) {
      for (; i < j; i++, j--)
        swap(a, i, j);
    }

    static void reverse(double[] a, int i, int j) {
      for (; i < j; i++, j--)
        swap(a, i, j);
    }

    static void reverse(char[] a, int i, int j) {
      for (; i < j; i++, j--)
        swap(a, i, j);
    }

    static void reverse(boolean[] a, int i, int j) {
      for (; i < j; i++, j--)
        swap(a, i, j);
    }

    static long sum(int[] a) {
      int sum = 0;
      for (int i : a)
        sum += i;
      return sum;
    }

    static long sum(long[] a) {
      long sum = 0;
      for (long i : a)
        sum += i;
      return sum;
    }

    static double sum(double[] a) {
      double sum = 0;
      for (double i : a)
        sum += i;
      return sum;
    }

    static int max(int[] a) {
      int max = Integer.MIN_VALUE;
      for (int i : a)
        if (i > max)
          max = i;
      return max;
    }

    static int min(int[] a) {
      int min = Integer.MAX_VALUE;
      for (int i : a)
        if (i < min)
          min = i;
      return min;
    }

    static long max(long[] a) {
      long max = Long.MIN_VALUE;
      for (long i : a)
        if (i > max)
          max = i;
      return max;
    }

    static long min(long[] a) {
      long min = Long.MAX_VALUE;
      for (long i : a)
        if (i < min)
          min = i;
      return min;
    }
  }
}
