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 FMain {
    String returnValue = "NoResult";
    PrintWriter out;
    Parser in;

    static Vector<Vertex> emptyVec = new Vector<Vertex>();

    static int counts[] = new int[256];
    static{
        for(int i = 0; i < 256; ++i){
            int cnt = 0;
            int tmp = i;
            while(tmp != 0){
                ++cnt;
                tmp &= tmp - 1;
            }
            counts[i] = cnt;
        }
    }

    class Vertex{
        int color;
        Set<Integer> colors = new HashSet<Integer>();
        Dictionary<Integer, Vector<Vertex>> edges = new Hashtable<Integer, Vector<Vertex>>();
        int[] byteColors;

        void setColor(int color){
            this.color = color;
            colors.add(color);
        }

        void addEdge(Vertex vertex, int color){
            Vector<Vertex> vec = edges.get(color);
            if(null == vec){
                vec = new Vector<Vertex>();
                edges.put(color, vec);
            }
            vec.add(vertex);
        }

        Vector<Vertex> getEdges(int color){
            Vector<Vertex> vec = edges.get(color);
            return vec == null ? emptyVec : vec;
        }

        public int[] getColors() {
            if(null == byteColors){
                byteColors = new int[maxColor / 8 + 1];
                for(int i : colors){
                    byteColors[i / 8] |= 1 << (i%8);
                }
            }
            return byteColors;
        }
    }

    int intersect(Vertex v1, Vertex v2){
        if(v1.colors.size() > v2.colors.size()) return intersect(v2, v1);
        int count = 0;
        if(v1.colors.size() > 30){
            int[] colors1 = v1.getColors();
            int[] colors2 = v2.getColors();
            for(int i = Math.min(colors1.length, colors2.length) - 1; i >= 0; --i){
                count += counts[colors1[i] & colors2[i]];
            }
        } else {
            for (int i : v1.colors) {
                if (v2.colors.contains(i)) ++count;
            }
        }
        return count;
    }

    Dictionary<Integer, Vector<Vertex>> col2v = new Hashtable<Integer, Vector<Vertex>>();
    int maxColor = 0;




    public void solve() {
        int n = in.nextInteger();
        int m = in.nextInteger();

        Vertex[] verts = new Vertex[n];


        for(int i = 0; i < n; ++i){
            verts[i] = new Vertex();
        }

        Hashtable<Integer, HashSet<Vertex>> col2v = new Hashtable<Integer, HashSet<Vertex>>();

        for(int i = 0; i < m; ++i){
            int a = in.nextInteger() - 1;
            int b = in.nextInteger() - 1;
            int c = in.nextInteger() - 1;
            verts[a].addEdge(verts[b], c);
            verts[b].addEdge(verts[a], c);
            HashSet<Vertex> vec = col2v.get(c);
            if(null == vec){
                vec = new HashSet<Vertex>();
                col2v.put(c, vec);
            }
            vec.add(verts[a]);
            vec.add(verts[b]);
        }

        for(int c : col2v.keySet()){
            HashSet<Vertex> vec = col2v.get(c);
            int startColor = maxColor;
            for(Vertex vrt : vec){
                if(vrt.color > startColor)continue;
                Stack<Vertex> stack = new Stack<Vertex>();
                stack.push(vrt);
                ++maxColor;
                while(!stack.empty()){
                    Vertex curr = stack.pop();
                    if(curr.color > startColor) continue;
                    curr.setColor(maxColor);
                    stack.addAll(curr.getEdges(c));
                }
            }
        }

        int qq = in.nextInteger();
        for(int q = 0; q < qq; ++q){
            int u = in.nextInteger() - 1;
            int v = in.nextInteger() - 1;

            out.println(intersect(verts[u], verts[v]));
        }
    }


    static public class Parser{
        Scanner scanner;

        public Parser() {
            scanner = new Scanner(System.in).useLocale(Locale.ENGLISH);
        }

        public Parser(String str) {
            scanner = new Scanner(str).useLocale(Locale.ENGLISH);
        }

        long nextLong(){
            return scanner.nextLong();
        }

        int nextInteger(){
            return scanner.nextInt();
        }

        double nextDouble(){
            return scanner.nextDouble();
        }

        String nextLine(){
            return scanner.nextLine();
        }

        String next(){
            return scanner.next();
        }

        int[] nextIntegers(int count){
            int[] result = new int[count];
            for(int i = 0; i < count; ++i){
                result[i] = nextInteger();
            }
            return result;
        }

        long[] nextLongs(int count){
            long[] result = new long[count];
            for(int i = 0; i < count; ++i){
                result[i] = nextLong();
            }
            return result;
        }

        int[][] nextIntegers(int fields, int count){
            int[][] result = new int[fields][count];
            for(int c = 0; c < count; ++c){
                for(int i = 0; i < fields; ++i){
                    result[i][c] = nextInteger();
                }
            }
            return result;
        }
    }

    void doReturn(){
        throw new RuntimeException();
    }

    void doReturn(String str){
        returnValue = str;
        doReturn();
    }

    void run(){
        in = new Parser();
        try{
            ByteArrayOutputStream outStream = new ByteArrayOutputStream();
            out = new PrintWriter(System.out);
            solve();
            out.close();
            System.out.print(outStream.toString());
        } catch (RuntimeException exc){
            System.out.print(returnValue);
        }
    }

    public static void main(String[] args) {
        new FMain().run();
    }
}
