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{
	static int[][] p, rank;
	static void dsu(int c,int n) {
		p[c] = new int[n];
		rank[c] = new int[n];
		for (int i = 0; i < n; i++) {  p[c][i] = i; }
	}
	static int findSet(int c,int i) { return p[c][i] == i ? i : (p[c][i] = findSet(c,p[c][i])); }
	
	static boolean isSameSet(int c,int i, int j) { return findSet(c,i) == findSet(c,j); }
	
	static void unionSet(int c,int i, int j) { 
		if (isSameSet(c,i, j)) 
			return;
		int x = findSet(c,i), y = findSet(c,j);
		if(rank[c][x] > rank[c][y]) { p[c][y] = x;}
		else
		{	p[c][x] = y;
			if(rank[c][x] == rank[c][y]) rank[c][y]++; 
		}
	}
	static void main() throws Exception{
		int n=sc.nextInt(),m=sc.nextInt();
		int[][]edges=new int[m][3];
		HashMap<Integer, Integer>[]maps=new HashMap[m];
		for(int i=0;i<m;i++) {
			edges[i]=new int[] {sc.nextInt()-1,sc.nextInt()-1,sc.nextInt()-1};
			maps[i]=new HashMap<Integer, Integer>();
		}
		for(int i=0;i<m;i++) {
			int x=edges[i][0],y=edges[i][1],c=edges[i][2];
			if(!maps[c].containsKey(x)) {
				maps[c].put(x, maps[c].size());
			}
			if(!maps[c].containsKey(y)) {
				maps[c].put(y, maps[c].size());
			}
		}
		p=new int[m][];
		rank=new int[m][];
		for(int i=0;i<m;i++) {
			if(maps[i].size()>0) {
				dsu(i, maps[i].size());
			}
		}
		HashSet<Integer>[]colHs=new HashSet[n];
		ArrayList<Integer>[]colAl=new ArrayList[n];
		for(int i=0;i<n;i++) {
			colHs[i]=new HashSet<Integer>();
			colAl[i]=new ArrayList<Integer>();
		}
		for(int i=0;i<m;i++) {
			int x=edges[i][0],y=edges[i][1],c=edges[i][2];
			unionSet(c,maps[c].get(x), maps[c].get(y));
			if(!colHs[x].contains(c)) {
				colHs[x].add(c);
				colAl[x].add(c);
			}
			if(!colHs[y].contains(c)) {
				colHs[y].add(c);
				colAl[y].add(c);
			}
		}
		HashMap<Long, Integer>memo=new HashMap<Long, Integer>();
		int q=sc.nextInt();
		for(int i=0;i<q;i++) {
			int u=sc.nextInt()-1,v=sc.nextInt()-1;
			long curHash=Math.min(u, v)*1l*n+Math.max(u, v);
			if(memo.containsKey(curHash)) {
				pw.println(memo.get(curHash));
				continue;
			}
			int ans=0;
			if(colAl[u].size()>colAl[v].size()) {
				int tmp=u;
				u=v;
				v=tmp;
			}
			for(int j=0;j<colAl[u].size();j++) {
				int c=colAl[u].get(j);
				if(maps[c].containsKey(v) && isSameSet(c,maps[c].get(u), maps[c].get(v))) {
					ans++;
				}
			}
			pw.println(ans);
			memo.put(curHash, ans);
		}
	}
	public static void main(String[] args) throws Exception {
		sc = new MScanner(System.in);
		pw = new PrintWriter(System.out);
//		int tc = 1;
//		tc=sc.nextInt();
//		while (tc-- > 0)
			main();
		pw.flush();
	}

	static PrintWriter pw;
	static MScanner sc;

	static class MScanner {
		StringTokenizer st;
		BufferedReader br;

		public MScanner(InputStream system) {
			br = new BufferedReader(new InputStreamReader(system));
		}

		public MScanner(String file) throws Exception {
			br = new BufferedReader(new FileReader(file));
		}

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

		public int[] intArr(int n) throws IOException {
			int[] in = new int[n];
			for (int i = 0; i < n; i++)
				in[i] = nextInt();
			return in;
		}

		public long[] longArr(int n) throws IOException {
			long[] in = new long[n];
			for (int i = 0; i < n; i++)
				in[i] = nextLong();
			return in;
		}

		public int[] intSortedArr(int n) throws IOException {
			int[] in = new int[n];
			for (int i = 0; i < n; i++)
				in[i] = nextInt();
			shuffle(in);
			Arrays.sort(in);
			return in;
		}

		public long[] longSortedArr(int n) throws IOException {
			long[] in = new long[n];
			for (int i = 0; i < n; i++)
				in[i] = nextLong();
			shuffle(in);
			Arrays.sort(in);
			return in;
		}

		public Integer[] IntegerArr(int n) throws IOException {
			Integer[] in = new Integer[n];
			for (int i = 0; i < n; i++)
				in[i] = nextInt();
			return in;
		}

		public Long[] LongArr(int n) throws IOException {
			Long[] in = new Long[n];
			for (int i = 0; i < n; i++)
				in[i] = nextLong();
			return in;
		}

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

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

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public char nextChar() throws IOException {
			return next().charAt(0);
		}

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

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

		public void waitForInput() throws InterruptedException {
			Thread.sleep(3000);
		}
	}

	static void shuffle(int[] in) {
		for (int i = 0; i < in.length; i++) {
			int idx = (int) (Math.random() * (i + 1));
			int tmp = in[i];
			in[i] = in[idx];
			in[idx] = tmp;
		}
	}

	static void shuffle(long[] in) {
		for (int i = 0; i < in.length; i++) {
			int idx = (int) (Math.random() * (i + 1));
			long tmp = in[i];
			in[i] = in[idx];
			in[idx] = tmp;
		}
	}
}