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



 public class Main {
	public static InputReader in;
    public static PrintWriter pw;
	public static void main(String args[]) {
		new Thread(null, new Runnable() {
            public void run() {
                try{
                    solve();
                }
                catch(Exception e){
                    e.printStackTrace();
                }
            }
        }, "1", 1 << 26).start();
    }
	//static TreeSet<Integer> set;
	static ArrayList<Integer> g[];
	static long edje=0;
    static boolean vis[];
	static int parent[];
	static int col[];
	static int Ans=0;
	static int min=Integer.MAX_VALUE;
	static int val[];
	static int degree[];
	//static int a[];
	static int f[];
	static Stack<Integer> stack;
	static boolean visited[];
    static int edjes=0;
    static int ar[][];
    static HashSet<Integer> set;
    static ArrayList<Integer> h[];
    static int a[][];
    static int count=0;
    static  ArrayList<Integer> two[][];
	public static void solve(){
	
		 in = new InputReader(System.in);
		 pw = new PrintWriter(System.out);
	     int n=in.nextInt();
	     int m=in.nextInt();
	     a=new int[101][101];
	     g=new ArrayList[n+1];
	     two=new ArrayList[n+1][n+1];
	     for(int i=0;i<=n;i++)
	     {
	    	 g[i]=new ArrayList<Integer>();
	     }
	     for(int i=0;i<=n;i++)
	     {
	    	 for(int j=0;j<=n;j++)
	    		 two[i][j]=new ArrayList<Integer>();
	     }
	     for(int i=0;i<m;i++)
	     {
	    	 int x=in.nextInt();
	    	 int y=in.nextInt();
	    	 int c=in.nextInt();
	    	 g[x].add(y);
	    	 g[y].add(x);
	    	 two[x][y].add(c);
	    	 two[y][x].add(c);
	     }
	     int q=in.nextInt();
	     //System.out.println(two[1][2]);
	     while(q-->0)
	     {
	    	 int x=in.nextInt();
	    	 int y=in.nextInt();
	    	 
	    	 int ans=0;
	    	 for(int col=1;col<=100;col++)
	    	 {
	    		vis=new boolean[n+1];
	    		if(dfs1(x,y,col))
	    			ans++;
	    	 }
	    	 System.out.println(ans);
	     }
	    
	}
  
public static boolean dfs1(int s,int t,int col)
{
	vis[s]=true;
	Stack<Integer> st=new Stack<Integer>();
	st.push(s);
	int temp=0;
	while(!st.isEmpty())
	{
		int top=st.pop();
		for(int p:g[top])
		{
			if(!vis[p]&&two[top][p].contains(col))
			{
				st.push(p);
				vis[p]=true;
			
			if(p==t)
			{
				return true;
			}
			}
		}
		
		}
return false;

}



/*	private static void TopologicalSort() 
	{
		for(int i=0;i<26;i++)
		{
			if(!visited[i]&&g[i].size()!=0)
			{
				dfs(i);
			}
		}
	}
	public static void dfs(int curr)
	{
		visited[curr]=true;
		for(int x:g[curr])
		{
			if(!visited[x])
				dfs(x);
		}
		stack.push(curr);
	}



	/*public static void dfs(int curr)
	{
		vis[curr]=true;
		int trees=0;
		for(int x:g[curr])
		{
			if(!vis[x]&&x!=1)
			{
			trees++;
			if(!s.contains(curr+" "+x))
				total+=cost[curr][x];
			dfs(x);
			}
	    }
		if(trees==0)
		{
			if(!s.contains(curr+" "+1))
				total+=cost[1][curr];
		}
	}
	public static void dfs1(int curr,int parent)
	{
	val[curr]=a[curr];
	for(int x:g[curr])
	{
	       if(x!=parent)
	       {
	    	   dfs1(x,curr);
	    	   val[curr]+=val[x];
	      }
	
	}
	}
	public static void dfs2(int curr,int parent)
	{
		f[curr]=val[curr];
		for(int x:g[curr])
		{
			if(x!=parent)
			{
				dfs2(x,curr);
				f[curr]+=f[x];
			}
		}
	}
	
	
	 
/*    public static void dfs2(int curr)
    {
    if(st[col[curr]].isEmpty())
    {
    ans[curr]=-1;	
    }
    else
    {
    	ans[curr]=st[col[curr]].peek();
    }
    st[col[curr]].push(curr);
    for(int x:g[curr])
    {
    	dfs2(x);
    }
    st[col[curr]].pop();
    	
    }
    
  
	public static void dfs1(int curr)
	{
		visited[curr]=true;
		for(int next:g[curr])
		{
			edje++;
			if(!visited[next])
				dfs1(next);
		}
	}
	
	public static void dfs(int curr,int prev)
		{
		val[curr]=1;
			for(int x:g[curr])
			{
				if(x!=prev)
				{
		            dfs(x,curr);
		            val[curr]+=val[x];
					
			    }
			}
		}*/


		public static long power(long a,long b)
		{
			long result=1;
			while(b>0)
			{
				if(b%2==1)
					result*=a;
				a=a*a;
				b/=2;
			}
			return result;
		}
				public static long pow(long n,long p,long m)
	{
		 long  result = 1;
		  if(p==0)
		    return 1;
		if (p==1)
		    return n;
		while(p!=0)
		{
		    if(p%2==1)
		        result *= n;
		    if(result>=m)
		    result%=m;
		    p >>=1;
		    n*=n;
		    if(n>=m)
		    n%=m;
		}
		return result;
	}
	static class Pair implements Comparable<Pair>{
	int day1;
		int day2;
		int val;
		Pair(int mr,int i){
	     	day1=mr;
	     	day2=i;
			
			
		}
		@Override
		public int compareTo(Pair o) {
		if(o.day1<this.day1)
		
			return 1;
			
			else 
				return -1;
			
			}
		
	}
	public static long gcd(long a, long b) {
		  if (b == 0) return a;
		  return gcd(b, a%b);
		}
	static class InputReader {
 
		private InputStream stream;
		private byte[] buf = new byte[8192];
		private int curChar, snumChars;
		private SpaceCharFilter filter;
 
		public InputReader(InputStream stream) {
			this.stream = stream;
		}
 
		public int snext() {
			if (snumChars == -1)
				throw new InputMismatchException();
			if (curChar >= snumChars) {
				curChar = 0;
				try {
					snumChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (snumChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}
 
		public   int nextInt() {
			int c = snext();
			while (isSpaceChar(c))
				c = snext();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = snext();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
 
		public long nextLong() {
			int c = snext();
			while (isSpaceChar(c))
				c = snext();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = snext();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = snext();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
 
		public int[] nextIntArray(int n) {
			int a[] = new int[n];
			for (int i = 0; i < n; i++)
				a[i] = nextInt();
			return a;
		}
 
		public String readString() {
			int c = snext();
			while (isSpaceChar(c))
				c = snext();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = snext();
			} while (!isSpaceChar(c));
			return res.toString();
		}
 
		public boolean isSpaceChar(int c) {
			if (filter != null)
				return filter.isSpaceChar(c);
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
 
		public interface SpaceCharFilter {
			public boolean isSpaceChar(int ch);
		}
	}
}
