Mr. Kitayuta has just bought an undirected graph consisting of 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 ≤ 100, 1 ≤ m ≤ 100), 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 ≤ 100), 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. 
2 1
1 2 1
1
1 2
 2 3
1 2 3
1 2 2
1 2 1
1
1 2
 2 5
1 2 1
1 2 2
1 2 3
1 2 4
1 2 5
1
1 2

1
 3
 5

import java.util.Scanner;

public class MainF {
	public static void main(String[] args) {
		int n, m, i;
		
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		m = sc.nextInt();
		
		// a disjoint set for each graph of a certain color
		DisjointSet[] coloredGraphs = new DisjointSet[m];
		
		for(i = 0; i < m; i++){
			int start = sc.nextInt();
			int end = sc.nextInt();
			int color = sc.nextInt();
			color--; // to make index start at 0
			
			if(coloredGraphs[color] == null){
				coloredGraphs[color] = new DisjointSet(n);
				coloredGraphs[color].initialize();
			}
			
			// add the edge to the set -- find if not equal then merge
			if(coloredGraphs[color].find(start-1) != coloredGraphs[color].find(end-1))
				coloredGraphs[color].merge(start-1, end-1);
		}
		
		String output = "";
		
		int queries = sc.nextInt();
		
		for(i = 0; i < queries; i++){
			int u = sc.nextInt();
			int v = sc.nextInt();			
			int answer = 0, j = 0;
			
			// assuming that colors are continuous--no colors skipped-- e.g 1,2,3,4 not 1,3,4
			while(coloredGraphs[j] != null){
				if(coloredGraphs[j].find(u-1) == coloredGraphs[j].find(v-1))
					answer++;
				j++;
			}
			
			output += (answer + "\n");
		}
		
		System.out.println(output);

	}
}

class DisjointSet {
	private int[] parents;
	private int[] rank;
	boolean initialized;

	public DisjointSet(int size) {
		parents = new int[size];
		rank = new int[size];
		initialized = false;
	}

	public void makeSet(int element) {
		parents[element] = element;
		rank[element] = 0;
	}

	void merge(int first, int second) {
		int parentX = find(first);
		int parentY = find(second);

		if (rank[parentX] >= rank[parentY])
			parents[parentY] = parentX;
		else if (rank[parentX] < rank[parentY])
			parents[parentX] = parentY;

		if (rank[parentX] == rank[parentY])
			rank[parentY]++;
	}

	int find(int element) {
		if (parents[element] == element)
			return element;
		return find(parents[element]);
	}

	boolean hasParent(int element) {
		return parents[element] == element ? false : true;
	}

	public void initialize() {
		int length = parents.length;

		for (int i = 0; i < length; i++) {
			parents[i] = i;
			rank[i] = 0;
		}
		initialized = true;
	}

}

class Edge implements Comparable<Edge> {
	int start, end, cost;

	public Edge(int start, int end, int cost) {
		this.start = start;
		this.end = end;
		this.cost = cost;
	}

	public int getCost() {
		return this.cost;
	}

	@Override
	public int compareTo(Edge o) {
		if(this.cost > o.cost)
			return 1;
		else if(this.cost == o.cost)
			return 0;
		else
			return -1;
	}
}