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. 
class CodeforcesTask505BSolution:
    def __init__(self):
        self.result = ''
        self.n_m = []
        self.edges = []
        self.q = 0
        self.queries = []

    def read_input(self):
        self.n_m = [int(x) for x in input().split(" ")]
        for x in range(self.n_m[1]):
            self.edges.append([int(y) for y in input().split(" ")])
        self.q = int(input())
        for x in range(self.q):
            self.queries.append([int(y) for y in input().split(" ")])

    def process_task(self):
        graphs = [[[] for x in range(self.n_m[0])] for c in range(self.n_m[1])]
        for edge in self.edges:
            graphs[edge[2] - 1][edge[0] - 1].append(edge[1])
            graphs[edge[2] - 1][edge[1] - 1].append(edge[0])
        results = []
        for query in self.queries:
            to_visit = [(query[0], c) for c in range(self.n_m[1])]
            used = set()
            visited = [[False] * self.n_m[0] for x in range(self.n_m[1])]
            while to_visit:
                visiting = to_visit.pop(-1)

                if visiting[1] not in used and not visited[visiting[1]][visiting[0] - 1]:
                    visited[visiting[1]][visiting[0] - 1] = True
                    if visiting[0] == query[1]:
                        used.add(visiting[1])
                    else:
                        to_visit.extend([(x, visiting[1]) for x in graphs[visiting[1]][visiting[0] - 1]])
            colors = len(used)
            results.append(colors)
        self.result = "\n".join([str(x) for x in results])

    def get_result(self):
        return self.result


if __name__ == "__main__":
    Solution = CodeforcesTask505BSolution()
    Solution.read_input()
    Solution.process_task()
    print(Solution.get_result())
