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.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Y {

	public static void main(String[] args) throws Exception{
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		DSU [] uf = new DSU[m];
		
		for(int i = 0 ; i <  m ; i ++)
			uf[i] = new DSU(n);
		
		
		for(int i = 0 ; i< m ; i++)
		{
			int u = sc.nextInt()-1;
			int v = sc.nextInt()-1;
			int index = sc.nextInt()-1;
			
			uf[index].union(u, v);
			
		}
		
		int q = sc.nextInt();
		StringBuilder st = new StringBuilder();
		while(q-->0)
		{
			int x = sc.nextInt()-1;
			int y = sc.nextInt()-1;
			int ans = 0;
			for(DSU d : uf)
				if(d.isSameSets(x, y))
					ans++;
			
			st.append(ans).append("\n");
		}
		System.out.print(st);
		

	}
	

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public boolean ready() throws IOException {
			return br.ready();
		}

	}


	static class DSU {
		
		int [] rank , p ;
		int sets ;
		public DSU(int n)
		{
			rank = new int [n];
			p = new int [n];
			for(int i = 0 ;i<n;i++)
				p[i] = i;
			
			sets = n ;
		}
		
		int findSets (int x) {
			return (p[x] == x) ? x :( p[x] = findSets( p[x])) ; 
		}
		
		boolean isSameSets(int x , int y )
		{
			return findSets(x) == findSets(y);
		}
		
		
		void union(int x , int y)
		{
			if(!isSameSets(x, y))
			{
				int i = findSets(x);
				int j = findSets(y);
				if(rank[i] >rank[j])
					p[j] = i ;
				else {
					p[i] = j;
					
					if(rank[i] == rank[j])
						rank[j]++;
					
				}
				
				
				
			}
			
		}



	}

}
