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

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author beginner1010
 */
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);
        TaskD solver = new TaskD();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskD {
        int[] visit;
        int[] parent;
        int[] height;

        int parent(int node, int color) {
            if (visit[node] < color) {
                height[node] = 0;
                parent[node] = node;
                visit[node] = color;
                return node;
            } else if (parent[node] == node) {
                return node;
            } else {
                return parent[node] = parent(parent[node], color);
            }
        }

        void join(int a, int b, int color) {
            int parA = parent(a, color);
            int parB = parent(b, color);
            if (parA == parB) return;
            if (height[parA] > height[parB]) {
                parent[parB] = parA;
            } else {
                parent[parA] = parB;
                if (height[parA] == height[parB]) height[parB]++;
            }
        }

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            int n = in.nextInt();
            int m = in.nextInt();

            ArrayList<Pair>[] edges = new ArrayList[m];
            for (int i = 0; i < m; i++) {
                edges[i] = new ArrayList<>();
            }
            for (int i = 0; i < m; i++) {
                int a = in.nextInt() - 1;
                int b = in.nextInt() - 1;
                int c = in.nextInt() - 1;
                edges[c].add(new Pair(a, b));
            }

            visit = new int[n];
            parent = new int[n];
            height = new int[n];
            HashSet<Pair>[] components = new HashSet[n];
            for (int i = 0; i < n; i++) {
                components[i] = new HashSet<>();
            }

            Arrays.fill(visit, -1);
            for (int color = 0; color < m; color++) {
                TreeSet<Integer> seenVertices = new TreeSet<>();
                for (Pair edge : edges[color]) {
                    join(edge.first, edge.second, color);
                    seenVertices.add(edge.first);
                    seenVertices.add(edge.second);
                }
                for (Integer vertex : seenVertices) {
                    components[vertex].add(new Pair(parent(vertex, color), color));
                }
            }

            HashMap<Pair, Integer> cacheQueries = new HashMap<>();
            int q = in.nextInt();
            for (int i = 0; i < q; i++) {
                int a = in.nextInt() - 1;
                int b = in.nextInt() - 1;
                if (components[a].size() > components[b].size() || (components[b].size() == components[a].size() && a > b)) {
                    a ^= b;
                    b ^= a;
                    a ^= b;
                }
                Pair query = new Pair(a, b);
                if (cacheQueries.containsKey(query)) {
                    out.println(cacheQueries.get(query));
                    continue;
                }
                int res = 0;
                for (Pair component : components[a]) {
                    if (components[b].contains(component))
                        res++;
                }
                out.println(res);
                cacheQueries.put(query, res);
            }
        }

    }

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

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

        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());
        }

    }

    static class Pair implements Comparable<Pair> {
        public int first;
        public int second;

        public Pair() {
        }

        public Pair(int first, int second) {
            this.first = first;
            this.second = second;
        }

        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Pair ii = (Pair) o;

            if (first != ii.first) return false;
            if (second != ii.second) return false;

            return true;
        }

        public int hashCode() {
            int result = first;
            result = 31 * result + second;
            return result;
        }

        public int compareTo(Pair o) {
            if (first != o.first) {
                return first < o.first ? -1 : 1;
            }
            if (second != o.second) {
                return second < o.second ? -1 : 1;
            }
            return 0;
        }

    }
}

