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. 
#include <bits/stdc++.h>
using namespace std;
int SQ, N, M, Q;
int E1[100002], E2[100002], col[100002];
int same[100002];
unordered_map<long long, int> S;
vector<int> W[100002];
int freq[100002], T[100002], H[100002];
int Q1[100002], Q2[100002];
int nodes[100002];
bool is[100002];
int result[100002];
int Find(int x) {
  if (T[x] != x) T[x] = Find(T[x]);
  return T[x];
}
void Union(int x, int y) { T[x] = y; }
void add(int x) {
  if (is[x] == false) {
    nodes[++nodes[0]] = x;
    is[x] = true;
  }
}
int main() {
  cin.sync_with_stdio(false);
  cin >> N >> M;
  while (SQ * SQ <= M) ++SQ;
  for (int i = 1; i <= M; ++i) {
    cin >> E1[i] >> E2[i] >> col[i];
    ++freq[col[i]];
    W[col[i]].push_back(i);
  }
  cin >> Q;
  for (int i = 1; i <= Q; ++i) {
    cin >> Q1[i] >> Q2[i];
    if (S.find(1LL * Q1[i] * (N + 1) + Q2[i]) != S.end())
      same[i] = S[1LL * Q1[i] * (N + 1) + Q2[i]];
    else {
      S[1LL * Q1[i] * (N + 1) + Q2[i]] = i;
      S[1LL * Q2[i] * (N + 1) + Q1[i]] = i;
    }
  }
  for (int i = 1; i <= N; ++i) T[i] = i;
  for (int i = 1; i <= M; ++i) {
    for (auto it = W[i].begin(); it != W[i].end(); ++it) {
      add(E1[*it]);
      add(E2[*it]);
      if (Find(E1[*it]) != Find(E2[*it])) Union(T[E1[*it]], T[E2[*it]]);
    }
    if (freq[i] >= SQ) {
      for (int j = 1; j <= Q; ++j)
        if (same[j] == 0 && Find(Q1[j]) == Find(Q2[j])) ++result[j];
    } else {
      for (int j = 1; j <= nodes[0]; ++j)
        for (int k = j + 1; k <= nodes[0]; ++k)
          if (Find(nodes[j]) == Find(nodes[k]))
            if (S.find(1LL * nodes[j] * (N + 1) + nodes[k]) != S.end())
              ++result[S[1LL * nodes[j] * (N + 1) + nodes[k]]];
    }
    for (auto it = W[i].begin(); it != W[i].end(); ++it) {
      T[E1[*it]] = E1[*it];
      T[E2[*it]] = E2[*it];
      is[E1[*it]] = 0;
      is[E2[*it]] = 0;
    }
    nodes[0] = 0;
  }
  for (int i = 1; i <= Q; ++i)
    if (same[i] != 0)
      cout << result[same[i]] << '\n';
    else
      cout << result[i] << '\n';
  return 0;
}
