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.File;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main{

	// split de array
	public static int[] readInts(String cad) {
		String read[] = cad.split(" ");
		int res[] = new int[read.length];
		for (int i = 0; i < read.length; i++) {
			res[i] = Integer.parseInt(read[i]);
		}
		return res;
	}

	public static class UF {
		final int MAX = 10000;
		public int padre[];
		public int rango[];

		public void MakeSet(int n) {
			padre = new int[n];
			rango = new int[n];
			for (int i = 0; i < n; ++i) {
				padre[i] = i; // Inicialmente el padre de cada vertice es el mismo
									// vertice
				rango[i] = 0; // Altura o rango de cada vertice es 0
			}
		}

		public int Find(int x) {
			if (x == padre[x]) { // Si estoy en la raiz
				return x; // Retorno la raiz
			}
			// else return Find( padre[ x ] ); //De otro modo busco el padre del
			// vertice actual, hasta llegar a la raiz.
			else
				return padre[x] = Find(padre[x]);
		}

		public void UnionbyRank(int x, int y) {
			int xRoot = Find(x);
			int yRoot = Find(y);
			if (rango[xRoot] > rango[yRoot]) {
				padre[yRoot] = xRoot;
			} else {

				padre[xRoot] = yRoot;
				if (rango[xRoot] == rango[yRoot]) {
					rango[yRoot]++;
				}
			}
		}

		public boolean sameComponent(int x, int y) {
			if (Find(x) == Find(y))
				return true;
			return false;
		}
	}

	public static void main(String[] args) throws IOException {
		long inicio = System.currentTimeMillis();
		StringBuilder out = new StringBuilder();
		BufferedReader in;
		File archivo = new File("entrada");
		if (archivo.exists())
			in = new BufferedReader(new FileReader(archivo));
		else
			in = new BufferedReader(new InputStreamReader(System.in));

		int k[] = readInts(in.readLine());
		int n = k[0];
		int m = k[1];
		UF colors[] = new UF[m+1];
		for (int i = 0; i < colors.length; i++) {
			colors[i] = new UF();
			colors[i].MakeSet(n);
		}
		for (int i = 0; i < m; i++) {
			k = readInts(in.readLine());
			int c = k[2];
			colors[c].UnionbyRank(k[0] - 1, k[1] - 1);
		}
		int q = Integer.parseInt(in.readLine());
		for (int i = 0; i < q; i++) {
			k = readInts(in.readLine());
			int cont = 0;
			for (int j = 0; j < colors.length; j++) {
				if (colors[j].sameComponent(k[0] - 1, k[1] - 1)) {
					cont++;
				}
			}
			out.append(cont + "\n");
		}
		System.out.print(out);
		if (archivo.exists())
			System.out.println("Tiempo transcurrido : "
					+ (System.currentTimeMillis() - inicio) + " milisegundos.");
	}
}
