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.BufferedWriter;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    
    static class DisjointSet
    {
        int[] parent, size;
        public DisjointSet(int n)
        {
            parent = new int[n];
            size = new int[n];
            for (int i=0; i<n; i++)
            {
                parent[i] = i;
                size[i] = 1;
            }
        }
        
        int root (int a)
        {
            while (parent[a]!=a)
            {
                parent[a] = parent[parent[a]];
                a = parent[a];
            }
            return a;
        }
        
        void union (int a, int b)
        {
            int rootA = root(a), rootB = root(b);
            if (rootA==rootB)
                return;
            if (size[rootA]<size[rootB])
            {
                parent[rootA] = rootB;
                size[rootB] += size[rootA];
            }
            else
            {
                parent[rootB] = rootA;
                size[rootA] += size[rootB];
            }
        }
        
        boolean find (int a, int b)
        {
            if (root(a)==root(b))
                return true;
            else
                return false;
        }
    }

    public static void main(String[] args) throws IOException {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(
                outputStream, "ASCII"));
        CustomScanner sc = new CustomScanner(inputStream);
        solve(sc, out);
        out.flush();
        out.close();
    }

    static void solve(CustomScanner sc, BufferedWriter out) throws IOException {
        int n = sc.nextInt(), m = sc.nextInt();
        DisjointSet[] dsu= new DisjointSet[m];
        for (int i=0; i<m; i++)
            dsu[i]=new DisjointSet(n+1);
        for (int i=0; i<m; i++)
        {
            int a=sc.nextInt(), b=sc.nextInt(), c=sc.nextInt();
            dsu[c-1].union(a, b);
        }
        int q = sc.nextInt();
        for (int i=0; i<q; i++)
        {
            int u=sc.nextInt(), v=sc.nextInt();
            int count = 0;
            for (int j=0; j<m; j++)
            {
                if (dsu[j].find(u, v))
                    count++;
            }
            out.write(Integer.toString(count));
            out.newLine();
        }
    }

    static class CustomScanner {
        BufferedReader br;
        StringTokenizer st;

        public CustomScanner(InputStream stream) {
            br = new BufferedReader(new InputStreamReader(stream));
        }

        private String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

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

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

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

        public String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }
}