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.*;
import java.io.*;
public class MrKitayutasColorfulGraph
{
	public static final int SQRT = 317;
	
	public static void main(String[] args) throws Exception
	{
		FastScanner in = new FastScanner(System.in);
//		PrintWriter out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
		PrintWriter out = new PrintWriter(System.out);
		
		int n = in.nextInt();
		int m = in.nextInt();
		
		ArrayList<Pair>[] edges = new ArrayList[m];
		HashSet<Integer>[] nodes = new HashSet[m];
		for(int x = 0; x < edges.length; x++)
		{
			edges[x] = new ArrayList<Pair>();
			nodes[x] = new HashSet<Integer>();
		}
		
		Random rand = new Random();
		
		for(int y = 0; y < m; y++)
		{
			int a = in.nextInt() - 1;
			int b = in.nextInt() - 1;
			int c = in.nextInt() - 1;
			
//			int a = 2 * y + 1;
//			int b = 2 * y + 2;
//			int c = rand.nextInt(178);
			
//			int a = 1;
//			int b = y + 2;
//			int c = rand.nextInt(310);
			
			edges[c].add(new Pair(a, b));
			nodes[c].add(a);
			nodes[c].add(b);
		}
		
		int q = in.nextInt();
		
		int[] answer = new int[q];
		HashMap<Query, Integer> ts = new HashMap<Query, Integer>();
		for(int z = 0; z < q; z++)
		{
			Query query = new Query(in.nextInt() - 1, in.nextInt() - 1);
//			Query query = new Query(1, z + 2);
			
			if(!ts.containsKey(query))
			{
				ts.put(query, z);
				answer[z] = z;
			}
			else
			{
				answer[z] = ts.get(query);
			}
		}
		
		int[] result = new int[q];
		ArrayList<DisjointSet> dss = new ArrayList<DisjointSet>();
		for(int a = 0; a < edges.length; a++)
		{
//			System.out.println(edges[a].size());
			
			DisjointSet ds = new DisjointSet(nodes[a]);
			
			for(Pair e : edges[a])
			{
				ds.union(e.a, e.b);
			}
			
			if(edges[a].size() < SQRT)
			{
				HashMap<Integer, ArrayList<Integer>> sets = new HashMap<Integer, ArrayList<Integer>>();
				for(int u : nodes[a]) {
					int set = ds.find(u);
					ArrayList<Integer> tmp = sets.get(set);
					if (tmp == null) {
						tmp = new ArrayList<Integer>();
						sets.put(set, tmp);
					}
					tmp.add(u);
				}
				for(int u : nodes[a])
				{
					for(int v : sets.get(ds.find(u)))
//					for(int v : nodes[a])
					{
						if (u==v)
							continue;
						Query query = new Query(u, v);
						Integer index = ts.get(query);
						if(index != null && ds.find(u) == ds.find(v))
						{
							result[index]++;
						}
					}
				}
			}
			else
			{
				dss.add(ds);
			}
		}
		
		for(Map.Entry<Query, Integer> entry : ts.entrySet())
		{
			for(DisjointSet ds : dss)
			{
				if(ds.find(entry.getKey().u) == ds.find(entry.getKey().v))
				{
					result[entry.getValue()]++;
				}
			}
		}
		
		for(int c = 0; c < result.length; c++)
		{
			out.println(result[answer[c]]);
		}
		
		out.close();
	}
	
	static class Pair
	{
		int a;
		int b;
		
		public Pair(int a, int b)
		{
			this.a = a;
			this.b = b;
		}
	}
	
	static class Query implements Comparable<Query>
	{
		int u;
		int v;
		
		public Query(int u, int v)
		{
			this.u = u;
			this.v = v;
		}
		
		public boolean equals(Object o)
		{
			Query q = (Query)o;
			return u == q.u && v == q.v;
		}
		
		public int compareTo(Query o)
		{
			if(u != o.u)
			{
				return u - o.u;
			}
			else
			{
				return v - o.v;
			}
		}
		
		public int hashCode()
		{
			return Arrays.hashCode(new int[] {u, v});
		}
	}
	
	static class DisjointSet
	{
		HashMap<Integer, Integer> parent;
		HashMap<Integer, Integer> rank;
		
		public DisjointSet(HashSet<Integer> nodes)
		{
			parent = new HashMap<Integer, Integer>();
			rank = new HashMap<Integer, Integer>();
			
			for(int node : nodes)
			{
				parent.put(node, node);
				rank.put(node, 0);
			}
		}
		
		public int find(int x)
		{
			Integer key = parent.get(x);
			if (key == null)
				return x;
			else {
				if (key != x) {
					int nk = find(key);
					parent.put(x, nk);
					return nk;
				} else
					return key;
			}
			/*
			if(!parent.containsKey(x))
			{
				return x;
			}
			else
			{
				if(parent.get(x) != x)
				{
					parent.put(x, find(parent.get(x)));
				}
				
				return parent.get(x);
			}
			*/
		}
		
		public boolean union(int x, int y)
		{
			int a = find(x);
			int b = find(y);
			
			if(a == b)
			{
				return false;
			}
			else
			{
				if(rank.get(a) < rank.get(b))
				{
					parent.put(a, b);
				}
				else if(rank.get(a) > rank.get(b))
				{
					parent.put(b, a);
				}
				else
				{
					parent.put(b, a);
					rank.put(a, rank.get(a) + 1);
				}
				
				return true;
			}
		}
	}
	
	static class FastScanner
	{
		BufferedReader br;
		StringTokenizer st;
		
		public FastScanner(InputStream input)
		{
			br = new BufferedReader(new InputStreamReader(input));
			st = new StringTokenizer("");
		}
		
		public String next() throws IOException
		{
			if(st.hasMoreTokens())
			{
				return st.nextToken();
			}
			else
			{
				st = new StringTokenizer(br.readLine());
				return next();
			}
		}
		
		public int nextInt() throws IOException
		{
			return Integer.parseInt(next());
		}
	}
}
