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. 
def get_connected_matrix(adjacency_matrix):
    n = len(adjacency_matrix)
    non_visited_vertices = set(i for i in range(n))
    cluster_numbers = [0] * n
    cluster_number = 1

    def traverse(u):
        non_visited_vertices.remove(u)
        cluster_numbers[u] = cluster_number
        for v in range(n):
            if v in non_visited_vertices:
                if adjacency_matrix[u][v]:
                    traverse(v)

    while non_visited_vertices:
        vertex = non_visited_vertices.pop()
        non_visited_vertices.add(vertex)
        traverse(vertex)
        cluster_number += 1

    connected_matrix = [[False] * n for _ in range(n)]

    for u in range(n):
        for v in range(n):
            if u == v:
                continue
            connected_matrix[u][v] = connected_matrix[v][u] = (cluster_numbers[u] == cluster_numbers[v])

    return connected_matrix


def main():
    n, m = [int(t) for t in input().split()]

    matrices = [[[False] * n for _ in range(n)] for _ in range(m)]

    for _ in range(m):
        a, b, c = [int(t) - 1 for t in input().split()]
        matrices[c][a][b] = True
        matrices[c][b][a] = True

    connected_matrices = [get_connected_matrix(matrix) for matrix in matrices]

    q = int(input())
    for _ in range(q):
        u, v = [int(t) - 1 for t in input().split()]
        total_connection = sum(1 for connected_matrix in connected_matrices if connected_matrix[u][v])
        print(total_connection)


if __name__ == '__main__':
    main()
