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.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.FileReader;
import java.util.Arrays;
import java.util.ArrayList;
import java.io.BufferedReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.io.*;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Jitendra Kushwaha
 */
public class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		FastScanner in = new FastScanner(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		TaskB solver = new TaskB();
		solver.solve(1, in, out);
		out.close();
	}
}

class TaskB {

    ArrayList<ArrayList<Integer>> g = new ArrayList<ArrayList<Integer>>();
    ArrayList<ArrayList<Integer>> c = new ArrayList<ArrayList<Integer>>();
    boolean[] used;
    public void solve(int testNumber, FastScanner in, PrintWriter out) {
        int n, m;
        n = in.nextInt(); m = in.nextInt();
        used = new boolean[n];
        for(int i = 0; i < n; i++) {
            g.add(new ArrayList<Integer>());
            c.add(new ArrayList<Integer>());
        }
        for(int i = 0; i < m; i++) {
            int u = in.nextInt();
            int v = in.nextInt();
            int x = in.nextInt();
            g.get(u - 1).add(v - 1);
            g.get(v - 1).add(u - 1);
            c.get(u - 1).add(x);
            c.get(v - 1).add(x);
        }
        int q = in.nextInt();
        for(int i = 0; i < q; i++) {
            int u = in.nextInt() - 1; int v = in.nextInt() - 1;
            int cnt = 0;
            for(int j = 1; j <= m; j++) {
                Arrays.fill(used, false);
                dfs(u, j);
                if(used[v]) {
                    cnt++;
                }
            }
            out.println(cnt);
        }
    }

    public void dfs(int u, int color) {
        used[u] = true;
        for(int i = 0; i < g.get(u).size(); i++) {
            int v = g.get(u).get(i);
            if(!used[v] && c.get(u).get(i) == color) {
                dfs(v, color);
            }
        }
    }
}

class FastScanner {
    // LOOK AT THAT SPEED. THAT SPEED.
    public static final int BASE_SPEED = 130;
    public static final int BUFFER_SIZE = 1 << 16;
    public static final char NULL_CHAR = (char) -1;

    BufferedInputStream in;
    StringBuilder str = new StringBuilder();
    byte[] buffer = new byte[BUFFER_SIZE];
    boolean EOF_FLAG = false;

    char c = NULL_CHAR;
    int bufferIdx = 0;
    int size = 0;

    public FastScanner(InputStream in) {
        this.in = new BufferedInputStream(in, BUFFER_SIZE);
    }

    public int nextInt() {
        long x = nextLong();
        if (x > Integer.MAX_VALUE || x < Integer.MIN_VALUE) {
            throw new ArithmeticException("Scanned value overflows integer");
        }
        return (int) x;
    }

    public long nextLong() {
        boolean negative = false;
        if (c == NULL_CHAR) {
            c = nextChar();
        }
        for (; !EOF_FLAG && (c < '0' || c > '9'); c = nextChar()) {
            if (c == '-') {
                negative = true;
            }               
        }
        checkEOF();
        long res = 0;
        for (; c >= '0' && c <= '9'; c = nextChar()) {
            res = (res << 3) + (res << 1) + c - '0';
        }
        return negative ? -res : res;
    }

    public String nextLine() {
        checkEOF();
        str.setLength(0);
        for (c = c == NULL_CHAR ? nextChar() : c; !EOF_FLAG && c != '\n'; c = nextChar()) {
            str.append(c);
        }
        c = NULL_CHAR;
        return str.toString();
    }

    public String next() {
        checkEOF();
        for (c = c == NULL_CHAR ? nextChar() : c; Character.isWhitespace(c); checkEOF()) {
            c = nextChar();
        }
        str.setLength(0);
        for (; !EOF_FLAG && !Character.isWhitespace(c); c = nextChar()) {
            str.append(c);
        }
        return str.toString();
    }

    public String nextOrNull() {
        try {
            return next();
        } catch (EndOfFileException e) {
            return null;
        }
    }

    public char peekChar() {
        if (c == NULL_CHAR) {
            c = nextChar();
        }
        return c;
    }

    public char nextChar() {
        if (EOF_FLAG) {
            return NULL_CHAR;
        }
        while (bufferIdx == size) {
            try {
                size = in.read(buffer);
                if (size == -1) {
                    throw new Exception();
                }
            } catch (Exception e) {
                EOF_FLAG = true;
                return NULL_CHAR;
            }
            if (size == -1) {
                size = BUFFER_SIZE;
            }
            bufferIdx = 0;
        }
        return (char) buffer[bufferIdx++];
    }

    public double nextDouble() {
        return Double.parseDouble(next());
    }
    
    public void checkEOF() {
        if (EOF_FLAG) {
            throw new EndOfFileException();
        }
    }

    @SuppressWarnings("serial")
    public class EndOfFileException extends RuntimeException {
    }
}


