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.IOException;
import java.io.PrintWriter;
import java.math.BigDecimal;
import java.math.MathContext;

import javax.swing.plaf.synth.SynthSeparatorUI;

import org.xml.sax.HandlerBase;

import java.util.*;

public class Main {
	
	static final int mod=(int)1e9+7;
	public static void main(String[] args) {
        FasterScanner s = new FasterScanner();
        PrintWriter out=new PrintWriter(System.out);
        
        
        int n=s.nextInt();
        int m=s.nextInt();
        
        DisjointSetsRank ds [] = new DisjointSetsRank[m];
        
        for(int i=0;i<m;i++){
        	ds[i]=new DisjointSetsRank(n+1);
        }
        for(int i=0;i<m;i++){
        	int a=s.nextInt();
        	int b=s.nextInt();
        	int c=s.nextInt();
        	ds[c-1].unite(a, b);
        }
        int q=s.nextInt();;
        while(q-->0){
        	
        	int a=s.nextInt();
        	int b=s.nextInt();
        	int ans=0;
        	for(int i=0;i<m;i++){
        		ans+=ds[i].sameSet(a, b);
        	}
        	System.out.println(ans);
        }
        
        out.close();
    }
    static boolean isPalin(String s){
    	for(int i=0,j=s.length()-1;i<s.length()/2;i++,j--){
    		if(s.charAt(i)!=s.charAt(j))
    			return false;
    	}
    	return true;
    }

    
    public static  class DisjointSetsRank {

    	int[] p;
    	int[] rank;

    	public DisjointSetsRank(int size) {
    		p = new int[size];
    		for (int i = 0; i < size; i++)
    			p[i] = i;
    		rank = new int[size];
    	}

    	public int root(int x) {
    		return x == p[x] ? x : (p[x] = root(p[x]));
    	}
    	public int sameSet(int x,int y){
    		if(root(x)==root(y))
    			return 1;
    		return 0;
    					
    	}
    	public void unite(int a, int b) {
    		a = root(a);
    		b = root(b);
    		if (a == b)
    			return;

    		if (rank[a] < rank[b]) {
    			p[a] = b;
    		} else {
    			p[b] = a;
    			if (rank[a] == rank[b])
    				++rank[a];
    		}
    	}

    	public static void main(String[] args) {
    		DisjointSetsRank ds = new DisjointSetsRank(10);
    		System.out.println(false == (ds.root(0) == ds.root(9)));
    		ds.unite(0, 9);
    		System.out.println(true == (ds.root(0) == ds.root(9)));
    	}
    }

    
    
    
    
    static class Pair<A extends Comparable<A> , B extends Comparable<B>>implements Comparable<Pair>{
    	A a;
    	B b;
    	public Pair(A a ,B b){ this.a =a; this.b = b; }

		public int compareTo(Pair o) {
			int res = a.compareTo((A) (o.a));
			if(res == 0)  
				res = b.compareTo((B)(o.b));
			return res;
		}
    	
    }
    
    static class Node
    {
    	int id=0;
    	char ch;
    	boolean done=false;
    	Node l,r;
    	int parent=0;
    	Node(char ch){ this.ch=ch;}
		
    }
    static int gcd (long m, long n){
        long x;
        long y;
        while(m%n != 0){
            x = n;
            y = m%n;
            m = x;
            n = y;
        }
        return (int) n;
    }

    
    
    
    public static class st {
    	
	    int n;
	    long[] val;
	    int[] index;
	    void build(long [] t) {  // build the tree
	       this.n=t.length;
	       val = new long[2*n];
	       index = new int[2*n];
	       
	       for(int i=0;i<n;i++){
	    	   val[n+i] = t[i];
	    	   index[n+i] = i;
	       }
	       for(int i=n-1;i>=0;i--){
	    	   if(val[2*i]>val[2*i+1]){
	    		   val[i] = val[2*i];
	    		   index[i]= index[2*i];
	    	   }
	    	   else{
	    		   val[i] = val[2*i+1];
	    		   index[i]= index[2*i+1];
	    	   }
	       }
	    }
	    
	    int query(int l, int r) {  // sum on interval [l, r)
	    	int res=0;
	    	long max=0;
	    	for (l += n, r += n; l < r; l >>= 1, r >>= 1) {
	    		if ((l&1)!=0) {
	    			if(val[l]>max){
	    				max=val[l];
	    				res = index[l];
	    			}
	    			l++;
	    		}
	            if ((r&1)!=0){
	            	--r;
	            	if(val[r]>max){
	    				max=val[r];
	    				res = index[r];
	    			}
	            }
	        }
	    	return res;
	    }
	}
    
  
   
   
   
   
   
   
   
   
   
   
    public static class FasterScanner {
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;

        public int read() {
            if (numChars == -1)
                throw new InputMismatchException();
            if (curChar >= numChars) {
                curChar = 0;
                try {
                    numChars = System.in.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (numChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public String nextLine() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isEndOfLine(c));
            return res.toString();
        }

        public String nextString() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = read();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public long nextLong() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public int nextInt() {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = read();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
          
        public int[] nextIntArray(int n) {
            int[] arr = new int[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nextInt();
            }
            return arr;
        }
      
        public long[] nextLongArray(int n) {
            long[] arr = new long[n];
            for (int i = 0; i < n; i++) {
                arr[i] = nextLong();
            }
            return arr;
        }

        private boolean isSpaceChar(int c) {
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        private boolean isEndOfLine(int c) {
            return c == '\n' || c == '\r' || c == -1;
        }
    }
}