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.util.*;

public class mr_kitayamas_colorful_graph
{
    static int n, m;

    static ArrayList<edge>[] c;

    @SuppressWarnings("unchecked")
    public static void main( String[] args )
    {
        Scanner in = new Scanner( System.in );
        n = in.nextInt();
        m = in.nextInt();
        c = (ArrayList<edge>[])new ArrayList<?>[n + 1];
        for ( int i = 1; i <= n; i++ )
            c[i] = new ArrayList<edge>();
        for ( int i = 0; i < m; i++ )
        {
            int u = in.nextInt(), v = in.nextInt(), co = in.nextInt();
            c[u].add( new edge( v, co ) );
            c[v].add( new edge( u, co ) );
        }
        int q = in.nextInt();
        for ( int i = 0; i < q; i++ )
        {
            int count = 0;
            int u = in.nextInt(), v = in.nextInt();
            for ( int j = 1; j <= m; j++ )
                if ( bfs( u, v, j ) )
                    count++;
            System.out.println( count );
        }
        in.close();
        System.exit( 0 );
    }

    public static boolean bfs( int u, int v, int co )
    {
        LinkedList<Integer> q = new LinkedList<Integer>();
        q.add( u );
        boolean[] visit = new boolean[n + 1];
        while ( !q.isEmpty() )
        {
            int cur = q.pop();
            ArrayList<edge> adj = c[cur];
            for ( int i = 0; i < adj.size(); i++ )
                if ( !visit[adj.get( i ).n] && adj.get( i ).c == co )
                    q.add( adj.get( i ).n );
            visit[cur] = true;
        }
        return visit[v];
    }
}

class edge
{
    int n, c;

    public edge( int n, int c )
    {
        this.n = n;
        this.c = c;
    }
}