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

public class CF0506D_MrKitayutaColorfulGraph {
	static class Scanner {
		BufferedReader br;
		StringTokenizer st;

		public Scanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}

		int nextInt() {
			return Integer.parseInt(next());
		}

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}

	}

	static int max(int a, int b) {
		return Math.max(a, b);
	}

	static int min(int a, int b) {
		return Math.min(a, b);
	}

	static void print(Object b) {
		System.out.print(b);
	}

	static void println(Object b) {
		System.out.println(b);
	}

	static void println() {
		System.out.println();
	}

	static class Node {
		boolean[][] b;
		int id;

		public Node(int i) {
			b = new boolean[100][100];
			id = i;
		}
	}

	static class UnionFind {
		private int[] id;
		private int[] sz;

		public UnionFind(int N) {
			id = new int[N];
			sz = new int[N];
			for (int i = 0; i < N; i++) {
				id[i] = i;
				sz[i] = 1;
			}
		}

		public int root(int i) {
			if (id[i] == i)
				return i;
			id[i] = root(id[i]);
			return id[i];
		}

		public boolean connected(int p, int q) {
			return root(p) == root(q);
		}

		public int size(int i) {
			return sz[root(i)];
		}

		public void union(int p, int q) {
			int a = Math.min(p, q);
			int b = Math.max(p, q);
			int i = root(a);
			int j = root(b);
			if (i == j)
				return;
			if (sz[i] < sz[j]) {
				id[i] = j;
				sz[j] += sz[i];
			} else {
				id[j] = i;
				sz[i] += sz[j];
			}

		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner scanner = new Scanner();
		int n = scanner.nextInt();
		int m = scanner.nextInt();
		UnionFind[] uf = new UnionFind[100];
		for (int i = 0; i < 100; i++)
			uf[i] = new UnionFind(n);
		for (int i = 0; i < m; i++) {
			int a = scanner.nextInt() - 1, b = scanner.nextInt() - 1, c = scanner.nextInt() - 1;
			uf[c].union(a, b);
		}
		int q = scanner.nextInt();
		for (int qe = 0; qe < q; qe++) {
			int ans = 0;
			int a = scanner.nextInt() - 1, b = scanner.nextInt() - 1;
			for (int i = 0; i < 100; i++) {
				if (uf[i].connected(a, b))
					ans++;
			}
			println(ans);
		}
	}

}
