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.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;


public class D {	
	BufferedReader reader;
    StringTokenizer tokenizer;
    PrintWriter out;
    
	public void solve() throws IOException {				
		int N = nextInt();
        int M = nextInt();
		ArrayList<int[]>[] edges = new ArrayList[M];
        for (int i = 0; i < M; i++) {
            edges[i] = new ArrayList<int[]>();
        }

        for (int i = 0; i < M; i++) {
            int v1 = nextInt() - 1;
            int v2 = nextInt() - 1;
            int c = nextInt() - 1;
            edges[c].add(new int[] {v1, v2});
        }

        HashSet<Integer>[] inGroups = new HashSet[N];
        for (int i = 0; i < N; i++) {
            inGroups[i] = new HashSet<Integer>();
        }

        int gpIndex = 0;
        for (int c = 0; c < M; c++) {
            HashMap<Integer, Integer> vertexes = new HashMap<Integer, Integer>();
            HashMap<Integer, Integer> vertexeReverses = new HashMap<Integer, Integer>();
            for (int[] edge: edges[c]) {
                if (!vertexes.containsKey(edge[0])) {
                    vertexes.put(edge[0], vertexes.size());
                }
                if (!vertexes.containsKey(edge[1])) {
                    vertexes.put(edge[1], vertexes.size());
                }
            }
            for (int key: vertexes.keySet()) {
                vertexeReverses.put(vertexes.get(key), key);
            }

            int NN = vertexes.size();
            int[] parents = new int[NN];
            int[] ranks = new int[NN];

            for (int i = 0; i < NN; i++) {
                parents[i] = i;
            }
            for (int[] edge: edges[c]) {
                int v1 = vertexes.get(edge[0]);
                int v2 = vertexes.get(edge[1]);
                union(parents, ranks, v1, v2);
            }

            HashMap<Integer, ArrayList<Integer>> gp = new HashMap<Integer, ArrayList<Integer>>();
            for (int i = 0; i < NN; i++) {
                int root = getRoot(parents, i);
                int v = vertexeReverses.get(i);
                if (!gp.containsKey(root)) {
                    gp.put(root, new ArrayList<Integer>());
                }
                gp.get(root).add(v);
            }


            for (int key: gp.keySet()) {
                for (int v: gp.get(key)) {
                    inGroups[v].add(gpIndex);
                }
                gpIndex++;
            }
        }

        HashMap<String, Integer> cache = new HashMap<String, Integer>();
        int Q = nextInt();
        for (int q = 0; q < Q; q++) {
            int v1 = nextInt() - 1;
            int v2 = nextInt() - 1;
            if (v1 > v2) {
                int tmp = v1;
                v1 = v2;
                v2 = tmp;
            }
            String key = v1 + "-" + v2;
            if (!cache.containsKey(key)) {
                int ans = 0;
                if (inGroups[v1].size() < inGroups[v2].size()) {
                    for (int vv: inGroups[v1]) {
                        if (inGroups[v2].contains(vv)) ans++;
                    }
                } else {
                    for (int vv: inGroups[v2]) {
                        if (inGroups[v1].contains(vv)) ans++;
                    }
                }
                cache.put(key, ans);

            }
            out.println(cache.get(key));
        }


//        for (int i = 0; i < N; i++) {
//            out.println(i + ": " + Arrays.toString(inGroups[i].toArray()));
//        }
	}

    public int getRoot(int[] parents, int node) {
        if (node != parents[node]) {
            parents[node] = getRoot(parents, parents[node]);
        }
        return parents[node];
    }

    public boolean isSameGroup(int[] parents, int n1, int n2) {
        return getRoot(parents, n1) == getRoot(parents, n2);
    }

    public void union(int[] parents, int[] ranks, int n1, int n2) {
        int root1 = getRoot(parents, n1);
        int root2 = getRoot(parents, n2);
        if (root1 == root2) return;

        if (ranks[root1] < ranks[root2]) {
            parents[root1] = root2;
        } else if (ranks[root2] < ranks[root1]) {
            parents[root2] = root1;
        } else {
            parents[root1] = root2;
            ranks[root2]++;
        }
    }

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		new D().run();
	}
	
	public void run() {
        try {
            reader = new BufferedReader(new InputStreamReader(System.in));
            tokenizer = null;
            out = new PrintWriter(System.out);
            solve();
            reader.close();
            out.close();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(1);
        }
    }

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

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

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

    String nextToken() throws IOException {
        while (tokenizer == null || !tokenizer.hasMoreTokens()) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        return tokenizer.nextToken();
    }

}
