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.*;
import java.util.*;

public class Main{
	public static class FastReader {
		BufferedReader br;
		StringTokenizer st;
		
 
		public FastReader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
 
		String next() {
			while (st == null || !st.hasMoreTokens()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (Exception r) {
					r.printStackTrace();
				}
			}
			return st.nextToken();
		}
 
		int nextInt() {
			return Integer.parseInt(next());
		}
 
		double nextDouble() {
			return Double.parseDouble(next());
		}
 
		long nextLong() {
			return Long.parseLong(next());
		}
 
		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (Exception r) {
				r.printStackTrace();
			}
			return str;
		}
	}
	
	public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
	static long mod = (long) (1e9+7);
    static final long N = (long) (1e15);
   
	public static void main(String[] args) {
		FastReader sc = new FastReader();
		
		  int n = sc.nextInt();
		  int m = sc.nextInt();
		  DJSet[] dsu = new DJSet[m+1];
		  for(int i=0;i<=m;++i) dsu[i] = new DJSet(n+1);
		  for(int i=1;i<=m;++i) {
			  int u = sc.nextInt();
			  int v = sc.nextInt();
			  int c = sc.nextInt();
			  dsu[c].union(u, v);
		  }
		  
		  int q = sc.nextInt();
		  while(q-->0) {
			  int ans = 0;
			  int u = sc.nextInt();
			  int v = sc.nextInt();
			  for(int i=1;i<=m;++i) {
				  if(dsu[i].find(u) == dsu[i].find(v)) ++ans;
			  }
			  out.println(ans);
		  }
		   out.close();			
		}

	static class DJSet
	{ 
	    int[] rank, parent; 
	    int n; 
	  
	    // Constructor 
	    public DJSet(int n) 
	    { 
	        rank = new int[n]; 
	        parent = new int[n]; 
	        this.n = n; 
	        makeSet(); 
	    } 
	  
	    // Creates n sets with single item in each 
	    void makeSet() 
	    { 
	        for (int i=0; i<n; i++) 
	        { 
	            // Initially, all elements are in 
	            // their own set. 
	            parent[i] = i; 
	        } 
	    } 
	  
	    
	    int find(int x) 
	    { 
	        
	        if (parent[x]!=x) 
	        { 
	             
	            parent[x] = find(parent[x]); 
	  
	           
	        } 
	  
	        return parent[x]; 
	    } 
	  
	    
	    void union(int x, int y) 
	    { 
	       
	        int xRoot = find(x), yRoot = find(y); 
	  
	        
	        if (xRoot == yRoot) 
	            return; 
	  
	        
	        if (rank[xRoot] < rank[yRoot]) 
	  
	          
	            parent[xRoot] = yRoot; 
	  
	      
	        else if (rank[yRoot] < rank[xRoot]) 
	   
	            parent[yRoot] = xRoot; 
	  
	        else 
	        { 
	           
	            parent[yRoot] = xRoot; 
	  
	            rank[xRoot] = rank[xRoot] + 1; 
	        } 
	    } 
	} 
	}
