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.*;
import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * Created by Snayde on 05.01.2015.
 */
public class Main {

    public static void solve() {
        int n = IO.readInt();
        int m = IO.readInt();

        graph = new List[n];
        for (int index = 0; index < n; ++index) {
            graph[index] = new ArrayList<Edge>();
        }
        while (m-- > 0) {
            int v1 = IO.readInt() - 1;
            int v2 = IO.readInt() - 1;
            int c = IO.readInt();

            Edge edge = new Edge(c, v1, v2);
            graph[v1].add(edge);
            graph[v2].add(edge);
        }
        marked = new boolean[n];

        int q = IO.readInt();
        int u, v;
        while (q-- > 0) {
            u = IO.readInt() - 1;
            v = IO.readInt() - 1;

            destination = v;
            colors = new ArrayList<Integer>();
            dfs(u, 0);
            IO.println(colors.size());
        }
    }

    private static List<Edge>[] graph;
    private static boolean[] marked;
    private static List<Integer> colors;
    private static int destination;

    private static void dfs(int vertex, int color) {
        if (vertex == destination) {
            colors.add(color);
            return;
        }

        marked[vertex] = true;
        for (Edge edge : graph[vertex]) {
            if ((color == 0 || color == edge.color) && !colors.contains(edge.color) && !marked[edge.another(vertex)]) {
                dfs(edge.another(vertex), edge.color);
            }
        }
        marked[vertex] = false;
    }

    private static class Edge {
        int color;
        int vertex1;
        int vertex2;

        Edge(int color, int vertex1, int vertex2) {
            this.color = color;
            this.vertex1 = vertex1;
            this.vertex2 = vertex2;
        }

        int another(int vertex) {
            return vertex == vertex1 ? vertex2 : vertex1;
        }

    }

    // Input/Output ================================

    public static class IO {

        private static Scanner scanner;
        private static PrintWriter writer;

        public static void setUp(InputStream in, OutputStream out) {
            scanner = new Scanner(new java.io.BufferedInputStream(in));
            writer = new PrintWriter(out);
        }

        public static boolean isEmpty() {
            return !scanner.hasNext();
        }

        public static boolean hasNextLine() {
            return scanner.hasNextLine();
        }

        public static String readLine() {
            String line;
            try {
                line = scanner.nextLine();
            } catch (Exception e) {
                line = null;
            }
            return line;
        }

        public static String readString() {
            return scanner.next();
        }

        public static int readInt() {
            return scanner.nextInt();
        }

        public static double readDouble() {
            return scanner.nextDouble();
        }

        public static float readFloat() {
            return scanner.nextFloat();
        }

        public static long readLong() {
            return scanner.nextLong();
        }

        public static void print(Object o) {
            writer.print(o);
            writer.flush();
        }

        public static void println(Object o) {
            writer.print(o + "\n");
            writer.flush();
        }
    }

    // Algorithms ================================

    private static class Algo {

        private static int binSearch(int[] array, int n, int lo, int hi) {
            if (lo > hi) {
                return lo;
            }

            int mid = lo + (hi - lo) / 2;
            int cmp = (int) Math.signum(n - array[mid]);
            if (cmp < 0) {
                return binSearch(array, n, lo, mid - 1);
            } else if (cmp == 0) {
                return mid;
            } else {
                return binSearch(array, n, mid + 1, hi);
            }
        }
    }

    public static final void main(String[] args) {
        IO.setUp(System.in, System.out);
        solve();
    }
}
