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.util.*;

public class D {
	@SuppressWarnings("unchecked")
	void run() {
		int n = in.nextInt();
		int T = 300;
		int m = in.nextInt();
		int[] a = new int[m];
		int[] b = new int[m];
		int[] c = new int[m];
		ArrayList<Integer>[] byColor = new ArrayList[m];
		for (int i = 0; i < m; i++) {
			byColor[i] = new ArrayList<Integer>();
		}
		for (int i = 0; i < m; i++) {
			a[i] = in.nextInt() - 1;
			b[i] = in.nextInt() - 1;
			c[i] = in.nextInt() - 1;
			byColor[c[i]].add(i);
		}
		int queries = in.nextInt();
		int[] x = new int[queries];
		int[] y = new int[queries];
		Map<Long, Integer> count = new TreeMap<Long, Integer>();
		for (int q = 0; q < queries; q++) {
			x[q] = in.nextInt() - 1;
			y[q] = in.nextInt() - 1;
			if (x[q] >= y[q]) {
				int t = x[q]; x[q] = y[q]; y[q] = t;
			}
			long enc = encode(x[q], y[q]);
			count.put(enc, 0);
		}
		int popular = 0;
		nei = new ArrayList[n];
		for (int i = 0; i < n; i++) {
			nei[i] = new ArrayList<Integer>();
		}
		comp = new int[n];
		Arrays.fill(comp, -1);
		for (int k = 0; k < m; k++) {
			if (byColor[k].size() >= T) {
				popular++;
			}
		}
		int[][] popColor = new int[n][popular];
		for (int k = 0, p = 0; k < m; k++) {
			if (byColor[k].size() < T) {
				TreeSet<Integer> actual = new TreeSet<Integer>(); 
				for (int i : byColor[k]) {
					nei[a[i]].add(b[i]);
					nei[b[i]].add(a[i]);
					actual.add(a[i]);
					actual.add(b[i]);
				}
				comps = 0;
				for (int i : actual) {
					if (comp[i] >= 0) {
						continue;
					}
					dfs(i);
					comps++;
				}
				for (int i : actual) {
					for (int j : actual) {
						if (i >= j || comp[i] != comp[j]) {
							continue;
						}
						long enc = encode(i, j);
						if (!count.containsKey(enc)) {
							continue;
						}
						count.put(enc, count.get(enc) + 1);
					}
				}				
				for (int i : actual) {
					nei[i].clear();
					comp[i] = -1;
				}
			} else {
				for (int i : byColor[k]) {
					nei[a[i]].add(b[i]);
					nei[b[i]].add(a[i]);
				}
				comps = 0;
				for (int i = 0; i < n; i++) {
					if (comp[i] >= 0) {
						continue;
					}
					dfs(i);
					comps++;
				}
				for (int i = 0; i < n; i++) {
					popColor[i][p] = comp[i];
				}
				for (int i = 0; i < n; i++) {
					nei[i].clear();
				}
				Arrays.fill(comp, -1);
				p++;
			}
		}
		for (int q = 0; q < queries; q++) {
			long enc = encode(x[q], y[q]);
			int res = count.get(enc);
			int[] cx = popColor[x[q]];
			int[] cy = popColor[y[q]];
			for (int i = 0; i < popular; i++) {
				if (cx[i] == cy[i]) {
					res++;
				}
			}
			out.println(res);
		}
	}
	
	long encode(int a, int b) {
		return b | ((long) a << 32);
	}
	
	ArrayList<Integer>[] nei;
	int[] comp;
	int comps;

	void dfs(int v) {
		comp[v] = comps;
		for (int u : nei[v]) {
			if (comp[u] >= 0) {
				continue;
			}
			dfs(u);
		}
	}
	
	static boolean stdStreams = true;
	static String fileName = D.class.getSimpleName().replaceFirst("_.*", "").toLowerCase();
	static String inputFileName = fileName + ".in";
	static String outputFileName = fileName + ".out";
	static MyScanner in;
	static PrintWriter out;

	public static void main(String[] args) throws IOException {
		Locale.setDefault(Locale.US);
		BufferedReader br;
		if (stdStreams) {
			br = new BufferedReader(new InputStreamReader(System.in));
			out = new PrintWriter(System.out);
		} else {
			br = new BufferedReader(new FileReader(inputFileName));
			out = new PrintWriter(outputFileName);
		}
		in = new MyScanner(br);
		int tests = 1;//in.nextInt();
		for (int test = 0; test < tests; test++) {
			new D().run();
		}
		br.close();
		out.close();
	}
	
	static class MyScanner {
		BufferedReader br;
		StringTokenizer st;

		MyScanner(BufferedReader br) {
			this.br = br;
		}
		
		void findToken() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					throw new RuntimeException(e);
				}
			}
		}
		
		String next() {
			findToken();
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		
		long nextLong() {
			return Long.parseLong(next());
		}
		
		double nextDouble() {
			return Double.parseDouble(next());
		}
	}
}
