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.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.*;

public class Main implements Runnable {

    class Dsuv {
        Dsuv link = this;
        int rank = 1;
        int color;
        Dsuv(int color) {
            this.color = color;
        }
        Dsuv get() {
            if (link == this) return this;
            return link = link.get();
        }
        void uni(Dsuv other) {
            Dsuv u = get(), v = other.get();
            if (u == v) return;
            if (u.rank == v.rank) u.rank++;
            if (u.rank > v.rank) {
                v.link = u;
            } else {
                u.link = v;
            }
        }
    }

    Map<Long, Dsuv> tm = new HashMap<Long, Dsuv>();
    ArrayList<Dsuv>[] alv = new ArrayList[100100];
    Map<Long, Integer> ans = new HashMap<Long, Integer>();

    Dsuv getv(int v, int c) {
        long vc = ((long)v << 20) + c;
        if (tm.containsKey(vc)) return tm.get(vc);
        Dsuv nv = new Dsuv(c);
        tm.put(vc, nv);
        alv[v].add(nv);
        return nv;
    }

    Dsuv getv2(int v, int c) {
        long vc = ((long)v << 20) + c;
        if (tm.containsKey(vc)) return tm.get(vc);
        return null;
    }

    void solve() {
        int n = nextInt();
        for (int i = 1; i <= n; i++) alv[i] = new ArrayList<Dsuv>();
        int m = nextInt();
        for (int i = 0; i < m; i++) {
            int a = nextInt(), b = nextInt(), c = nextInt();
            getv(a, c).uni(getv(b, c));
        }
        int q = nextInt();
        for (int i = 0; i < q; i++) {
            int a = nextInt(), b = nextInt();
            if (alv[a].size() > alv[b].size() || alv[a].size() == alv[b].size() && a > b) {
                int t = a; a = b; b = t;
            }
            long ab = ((long)a << 20) + b;
            int res = 0;
            if (!ans.containsKey(ab)) {
                for (Dsuv u : alv[a]) {
                    Dsuv v = getv2(b, u.color);
                    if (v == null) continue;
                    if (u.get() == v.get()) res++;
                }
                ans.put(ab, res);
            } else res = ans.get(ab);
            out.println(res);
        }
    }

    int nextInt() {
        return Integer.parseInt(nextToken());
    }
    String nextToken() {
        try {
            while (st == null || !st.hasMoreTokens()) st = new StringTokenizer(in.readLine());
            return st.nextToken();
        } catch (Exception e) {
            return null;
        }
    }
    BufferedReader in;
    PrintWriter out;
    StringTokenizer st;
    public void run() {
        try {
            in = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
            solve();
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(1);
        } finally {
            out.close();
        }
    }
    public static void main(String[] args) {
        new Thread(null, new Main(), "name", 1 << 28).start();
    }
}
