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 D implements Runnable {
	public static void main (String[] args) {new Thread(null, new D(), "_cf", 1 << 28).start();}

	public void run() {
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		System.err.println("");

		int n = fs.nextInt(), m = fs.nextInt();
		int[][] edges = new int[m][5];
		int[] deg = new int[n];
		for(int i = 0; i < m; i++) {
			for(int j = 0; j < 2; j++) {
				edges[i][j] = fs.nextInt()-1;
				deg[edges[i][j]]++;
			}
			edges[i][2] = fs.nextInt();
			edges[i][3] = i;
		}
		Edge[][] adj = new Edge[n][];
		for(int i = 0; i < n; i++) {
			adj[i] = new Edge[deg[i]];
			deg[i] = 0;
		}
		
		for(int i = 0; i < m; i++) {
			int u = edges[i][0], v = edges[i][1];
			int color = edges[i][2];
			adj[u][deg[u]] = new Edge(v, color, i);
			adj[v][deg[v]] = new Edge(u, color, i);
			deg[u]++; deg[v]++;
		}
		
		int q = fs.nextInt();
		int[][] queries = new int[q][3];
		for(int i = 0; i < q; i++) {
			for(int j = 0; j < 2; j++) {
				queries[i][j] = fs.nextInt()-1;
			}
			if(queries[i][0] < queries[i][1]) {
				int temp = queries[i][0];
				queries[i][0] = queries[i][1];
				queries[i][1] = temp;
			}
			queries[i][2] = i;
		}
		
		for(int i = 0; i < n; i++) {
			Arrays.sort(adj[i]);
		}
		Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2]));
		
		for(int i = 0; i < m; i++) edges[i][4] = i;
		
		boolean[] used = new boolean[m];
		int[] queue = new int[2*Math.max(n, m)];
		int[] visTime = new int[n];
		int curColor = 1;
		ArrayList<Integer>[] allTimes = new ArrayList[n];
		for(int i = 0; i < n; allTimes[i++] = new ArrayList<>());
		HashMap<Integer, Integer>[] maps = new HashMap[n];
		for(int i = 0; i < n; i++) maps[i] = new HashMap<>();
		for(int i = 0; i < n; i++) {
			for(int j = 0; j < adj[i].length; j++) {
				int col = adj[i][j].color;
				if(!maps[i].containsKey(col)) maps[i].put(col, j);
			}
		}
		
		for(int i = 0; i < edges.length; i++) {
			int upTo = i;
			while(upTo < edges.length && edges[i][2] == edges[upTo][2]) {
				upTo++;
			}
			for(int k = i; k < upTo; k++) {
				int id = edges[k][3];
				if(used[id]) continue;
				int tail = 0;
				queue[tail++] = edges[k][0];
				queue[tail++] = edges[k][1];
				visTime[edges[k][0]] = curColor;
				visTime[edges[k][1]] = curColor;
				used[id] = true;
				
				for(int j = 0; j < tail; j++) {
					int u = queue[j];
					allTimes[u].add(curColor);
					int startIdx = maps[u].get(edges[i][2]);
					for(int ii = startIdx; ii < adj[u].length; ii++) {
						if(adj[u][ii].color != edges[i][2]) break;
						int v = adj[u][ii].to;
						if(used[adj[u][ii].id]) continue;
						used[adj[u][ii].id] = true;
						if(visTime[v] == curColor) continue;
						visTime[v] = curColor;
						queue[tail++] = v;
					}
				}
				curColor++;
			}
			i = --upTo;
		}
		
		Arrays.sort(queries, (a, b) -> Integer.compare(a[0], b[0]) == 0 ? Integer.compare(a[1], b[1]) : Integer.compare(a[0], b[0]));
		
		for(int i = 0; i < n; i++) {
			maps[i].clear();
			for(int j : allTimes[i]) maps[i].put(j, 0);
		}
		int[] res = new int[q];
		for(int i = 0; i < q; i++) {
			int upTo = i;
			while(upTo < q && queries[i][0] == queries[upTo][0] && queries[i][1] == queries[upTo][1]) upTo++;
			int u = queries[i][0];
			int v = queries[i][1];
			if(adj[v].length < adj[u].length) {
				int temp = v;
				v = u; u = temp;
			}
			int ret = 0;
			for(int time : allTimes[u]) {
				if(maps[v].containsKey(time)) ret++;
			}
			for(int j = i; j < upTo; j++) res[queries[j][2]] = ret;
			i = --upTo;
		}
		for(int i : res) out.println(i);
		
		out.close();
	}
	
	boolean find(ArrayList<Integer> a, int key) {
		int lo = 0, hi = a.size()-1;
		for(int bs = 0; bs < 50 && lo <= hi; bs++) {
			int mid = (lo+hi)/2;
			int x = a.get(mid);
			if(x > key) hi = mid-1;
			else if(x < key) lo = mid+1;
			else return true;
		}
		return false;
	}
	
	int find(Edge[] a, int color, boolean x) {
		int lo = 0, hi = a.length-1;
		int ret = -1;
		for(int bs = 0; bs < 50 && lo <= hi; bs++) {
			int mid = (lo+hi)/2;
			if(a[mid].color > color) {
				hi = mid-1;
			}
			else if(a[mid].color < color) {
				lo = mid+1;
			}
			else {
				ret = mid;
				if(!x) hi = mid-1;
				else lo = mid+1;
			}
		}
		return ret;
	}
	
	class Edge implements Comparable<Edge> {
		int to, color, id;
		Edge(int t, int c, int i) {
			to = t;
			color = c;
			id = i;
		}
		public int compareTo(Edge e) {
			return Integer.compare(color, e.color);
		}
	}

	class FastScanner {
		public int BS = 1<<16;
		public char NC = (char)0;
		byte[] buf = new byte[BS];
		int bId = 0, size = 0;
		char c = NC;
		double num = 1;
		BufferedInputStream in;

		public FastScanner() {
			in = new BufferedInputStream(System.in, BS);
		}

		public FastScanner(String s) {
			try {
				in = new BufferedInputStream(new FileInputStream(new File(s)), BS);
			}
			catch (Exception e) {
				in = new BufferedInputStream(System.in, BS);
			}
		}

		public char nextChar(){
			while(bId==size) {
				try {
					size = in.read(buf);
				}catch(Exception e) {
					return NC;
				}                
				if(size==-1)return NC;
				bId=0;
			}
			return (char)buf[bId++];
		}

		public int nextInt() {
			return (int)nextLong();
		}

		public long nextLong() {
			num=1;
			boolean neg = false;
			if(c==NC)c=nextChar();
			for(;(c<'0' || c>'9'); c = nextChar()) {
				if(c=='-')neg=true;
			}
			long res = 0;
			for(; c>='0' && c <='9'; c=nextChar()) {
				res = (res<<3)+(res<<1)+c-'0';
				num*=10;
			}
			return neg?-res:res;
		}

		public double nextDouble() {
			double cur = nextLong();
			return c!='.' ? cur:cur+nextLong()/num;
		}

		public String next() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c>32) {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public String nextLine() {
			StringBuilder res = new StringBuilder();
			while(c<=32)c=nextChar();
			while(c!='\n') {
				res.append(c);
				c=nextChar();
			}
			return res.toString();
		}

		public boolean hasNext() {
			if(c>32)return true;
			while(true) {
				c=nextChar();
				if(c==NC)return false;
				else if(c>32)return true;
			}
		}
		
		public int[] nextIntArray(int n) {
			int[] res = new int[n];
			for(int i = 0; i < n; i++) res[i] = nextInt();
			return res;
		}
		
	}

}