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.*;
public class b {
	public static void main(String[] arg)
	{
		new b();
	}
	public b()
	{
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		int m = in.nextInt();
		ArrayList<ArrayList<Pair>> eList = new ArrayList<ArrayList<Pair>>();
		for(int i = 0; i <= n; i++)
		{
			eList.add(new ArrayList<Pair>());
			
		}
		for(int i = 0; i < m; i++)
		{
			int v1 = in.nextInt();
			int v2 = in.nextInt();
			int color = in.nextInt();
			eList.get(v1).add(new Pair(v2, color));
			eList.get(v2).add(new Pair(v1, color));
		}
		int query = in.nextInt();
		for(int p = 0; p < query; p++)
		{
			int start = in.nextInt();
			int end = in.nextInt();
			int answer = 0;
			for(int c = 1; c <= m; c++)
			{
				ArrayDeque<Pair> q = new ArrayDeque<Pair>();
				HashSet<Integer> used = new HashSet<Integer>();
				boolean possible = false;
				for(int i = 0; i < eList.get(start).size(); i++)
				{
					if(eList.get(start).get(i).color == c)
						q.add(eList.get(start).get(i));
				}
				while(q.size() > 0)
				{
					Pair temp = q.poll();
					
					if(!used.add(temp.v)) continue;
					if(temp.color != c) continue;
					if(temp.v == end)
					{
						possible = true;
						break;
					}
					for(int i = 0; i < eList.get(temp.v).size(); i++)
					{
						if(eList.get(temp.v).get(i).color == c)
							q.add(eList.get(temp.v).get(i));
					}
				}
				if(possible) answer++;
			}
			System.out.println(answer);
		}
		in.close();
	}
	class Pair
	{
		int v;
		int color;
		public Pair(int a, int b)
		{
			v = a;
			color = b;
		}
	}
}
