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.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;

public class KitayutasColorfulGraph {

	private static class ColorfulGraph {

		private static class Vertice {

			private final Map<Integer, Set<Vertice>> connections = new HashMap<>();

			private final Map<Integer, Set<Vertice>> connectedComponents = new HashMap<>();

			public void connectWithColor(Vertice o, int color) {
				connectWithColorInternal(o, color, true);
			}

			private void connectWithColorInternal(Vertice o, int color, boolean needsBidirectional) {
				Set<Vertice> connectionsForColor = connections.getOrDefault(color, new HashSet<>());
				connectionsForColor.add(o);
				connections.put(color, connectionsForColor);
				if (needsBidirectional) {
					o.connectWithColorInternal(this, color, false);
				}
			}

			public int numColorsConnectingTo(Vertice o) {
				int count = 0;
				for (Set<Vertice> connectedComponent : connectedComponents.values()) {
					if (connectedComponent.contains(o)) {
						count++;
					}
				}
				return count;
			}

			public void setConnectedComponentForColor(Set<Vertice> connectedComponent, int color) {
				connectedComponents.put(color, connectedComponent);
			}

			public Set<Vertice> connectedWithColor(int color) {
				return connections.getOrDefault(color, new HashSet<>());
			}

		}

		private static class Builder {

			private final Map<Integer, Vertice> lookupTable = new HashMap<>();

			private final Set<Integer> colors = new HashSet<>();

			public void addEdgeWithColor(int v1, int v2, int color) {
				// Create new vertices if necessary.
				Vertice v1Node = lookupTable.getOrDefault(v1, new Vertice());
				Vertice v2Node = lookupTable.getOrDefault(v2, new Vertice());
				v1Node.connectWithColor(v2Node, color);
				lookupTable.put(v1, v1Node);
				lookupTable.put(v2, v2Node);
				// Update the colors we've seen so far.
				colors.add(color);
			}

			public ColorfulGraph build() {
				for (int color : colors) {
					// Keep track of all the nodes we've explored to generate all connected
					// components for this color.
					Set<Vertice> nodesExplored = new HashSet<>();
					for (Vertice vertice : lookupTable.values()) {
						// Check that this node was not already added in a previous connected component.
						if (!nodesExplored.contains(vertice)) {
							Set<Vertice> connectedComponent = new HashSet<>();
							getConnectedComponent(connectedComponent, vertice, color, nodesExplored);
							// Update all the nodes in that component so they know they are connected to
							// each other.
							for (Vertice inComponent : connectedComponent) {
								inComponent.setConnectedComponentForColor(connectedComponent, color);
							}
						}
					}
				}
				return new ColorfulGraph(lookupTable);
			}

			private void getConnectedComponent(Set<Vertice> connectedComponent, Vertice vertice, int color,
					Set<Vertice> nodesExplored) {
				nodesExplored.add(vertice);
				Set<Vertice> connections = vertice.connectedWithColor(color);
				if (connections.isEmpty()) {
					// This case should only happen when we start our search with a vertice with no
					// connections of this color.
					return;
				}
				connectedComponent.add(vertice);
				for (Vertice connected : connections) {
					if (!connectedComponent.contains(connected)) {
						getConnectedComponent(connectedComponent, connected, color, nodesExplored);
					}
				}
			}

		}

		private final Map<Integer, Vertice> lookupTable;

		private ColorfulGraph(Map<Integer, Vertice> lookupTable) {
			this.lookupTable = lookupTable;
		}

		public int numColorsConnecting(int v1, int v2) {
			Vertice v1Node = lookupTable.get(v1);
			Vertice v2Node = lookupTable.get(v2);
			if (v1Node == null || v2Node == null) {
				// If either node is not in the table, then it has no edges and therefore there
				// is no path connecting between them.
				return 0;
			}
			return v1Node.numColorsConnectingTo(v2Node);
		}

		public static Builder builder() {
			return new Builder();
		}
	}

	public static void main(String[] args) {
		try (Scanner s = new Scanner(System.in)) {
			ColorfulGraph.Builder graphBuilder = ColorfulGraph.builder();
			s.nextInt();
			int numEdges = s.nextInt();
			for (int i = 0; i < numEdges; i++) {
				graphBuilder.addEdgeWithColor(s.nextInt(), s.nextInt(), s.nextInt());
			}
			ColorfulGraph graph = graphBuilder.build();
			int numQueries = s.nextInt();
			for (int i = 0; i < numQueries; i++) {
				System.out.println(graph.numColorsConnecting(s.nextInt(), s.nextInt()));
			}
		}
	}

}
