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.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Random;
import java.util.Scanner;
import java.util.Stack;
import java.util.StringTokenizer;
import java.util.TreeSet;
import java.util.concurrent.LinkedBlockingDeque;

import javax.swing.border.Border;

public class a {

	public static long mod = (long) Math.pow(10, 9) + 7;
	public static int k = 0;

	private static class node {
		int node;
		int c;

		node(int n, int c) {
			node = n;
			this.c = c;
		}

	}

	public static class point implements Comparable<point> {
		long x;
		long y;
		long b;

		point(long x, long y, long b) {
			this.x = x;
			this.y = y;
			this.b = b;
		}

		@Override
		public int compareTo(point o) {
			if (k == 0)
				return (int) (o.x - x);
			else
				return (int) (y - o.y);

		}
	}

	public static int ch(long y) {
		int r = Long.bitCount(y);
		return r;
	}

	public static long gcd(long x, long y) {
		if (y == 0)
			return x;

		return gcd(y, x % y);
	}

	public static boolean ch[] = new boolean[10000005];
	public static ArrayList<Integer> prime = new ArrayList();

	// public static Queue<Integer> pp;

	public static void sieve(int k) {
		ch[0] = ch[1] = true;

		for (int i = 2; i <= k; i++) {
			if (!ch[i]) {
				prime.add(i);
				// pp.add(i);
				for (long j = (long) i * (long) i; j <= k; j += i) {
					ch[(int) j] = true;
				}
			}
		}

	}

	public static long pw(int x, int power, int mod) {
		if (power == 1)
			return x % mod;
		else if (power % 2 == 0)
			return pw((x % mod * x % mod) % mod, power / 2, mod);
		else
			return (pw(x, power - 1, mod) % mod * x % mod) % mod;

	}

	public static ArrayList<node> graph[];

	public static int bfs(int s, int e, int n, int m) {
		boolean ok[][] = new boolean[n + 1][m + 1];
		Queue<node> q = new LinkedList<>();
		int ans = 0;
		q.add(new node(s, 0));
		ok[s][0] = true;
		while (!q.isEmpty()) {
			node ee = q.poll();
			int node = ee.node;
			int c = ee.c;
			if (node == e) {
				//System.out.println(c);
				ans++;
			}
			for (int i = 0; i < graph[node].size(); i++) {
				int w = graph[node].get(i).node;
				int col = graph[node].get(i).c;
				if (c == 0&&!ok[w][col]) {
					ok[w][col]=true;
					q.add(new node(w, col));
				} else if (c == col && !ok[w][col]) {
					ok[w][col] = true;
					q.add(new node(w, col));
				}
			}
		}
		return ans;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		// BufferedReader in = new BufferedReader(new FileReader(
		// "in.txt"));
		StringBuilder qq = new StringBuilder();
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		// PrintWriter out = new PrintWriter(new FileWriter("out.txt"));

		String y[] = in.readLine().split(" ");
		int n = Integer.parseInt(y[0]);
		int m = Integer.parseInt(y[1]);
		graph = new ArrayList[n + 2];
		for (int i = 0; i < n + 2; i++) {
			graph[i] = new ArrayList();
		}
		for (int i = 0; i < m; i++) {
			y = in.readLine().split(" ");
			int a = Integer.parseInt(y[0]);
			int b = Integer.parseInt(y[1]);
			int c = Integer.parseInt(y[2]);
			graph[a].add(new node(b, c));
			graph[b].add(new node(a, c));
		}
		int q=Integer.parseInt(in.readLine());
		for (int i = 0; i <q ; i++) {
			y=in.readLine().split(" ");
			int a = Integer.parseInt(y[0]);
			int b = Integer.parseInt(y[1]);
			out.println(bfs(a,b,n,m));
		}
		out.close();

	}
}
