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. 
"""
Since neither the graph nor the number of queries is too large, for each 
query you can simply count the number of the "good" colors 
(the colors that satisfies the condition) by checking if each color is 
"good". To do that, you can perform Depth First Search (or Breadth First Search)
and verify whether you can reach vi from ui traversing only the edges of that 
color. If you prefer using Union-Find, it will also do the job.
"""
from collections import defaultdict


def dfs(graph, start, end, visited, color):
    q = [start]
    while q:
        node = q.pop()
        visited[node] = True

        if node == end:
            break

        for v in graph[color][node]:
            if not visited[v]:
                q.append(v)


def has_path(graph, start, end, visited, color):
    for i in range(len(visited)):
        visited[i] = False

    dfs(graph, start, end, visited, color)
    return visited[end]


n, m = map(int, input().split())
    
graph = defaultdict(lambda: defaultdict(list))

for _ in range(m):
    a, b, c = map(int, input().split())
    a -= 1
    b -= 1

    graph[c][a].append(b)
    graph[c][b].append(a)

visited = [False] * n
    
q = int(input())

for _ in range(q):
    u, v = map(int,input().split())
    u -= 1
    v -= 1
    ans = 0

    for c in graph.keys():
        if has_path(graph, u, v, visited, c):
            ans += 1

    print(ans)
