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>
const int MAXN = 1e5 + 10;
const int BLO = 310;
std::vector<std::pair<int, int> > es[MAXN];
int xs[MAXN], ys[MAXN];
int ansl[MAXN];
std::vector<int> qs[MAXN], cs[MAXN];
int n, m, Q;
std::vector<int> out[MAXN];
int bel[MAXN];
int ta[MAXN];
int li[MAXN << 1], bak;
void bfs(int u, int idx) {
  static std::queue<int> q;
  q.push(u);
  bel[u] = idx;
  while (!q.empty()) {
    int t = q.front();
    q.pop();
    ++ta[t];
    li[++bak] = t;
    for (int i : out[t])
      if (!bel[i]) bel[i] = idx, q.push(i);
  }
}
void addcol(int i) {
  for (auto j : es[i]) {
    out[j.first].push_back(j.second);
    out[j.second].push_back(j.first);
  }
}
void delcol(int i) {
  for (auto j : es[i]) {
    out[j.first].clear();
    out[j.second].clear();
    bel[j.first] = 0;
    bel[j.second] = 0;
  }
}
int main() {
  std::ios_base::sync_with_stdio(false), std::cin.tie(0);
  std::cin >> n >> m;
  for (int i = 1, b, e, v; i <= m; ++i) {
    std::cin >> b >> e >> v;
    es[v].emplace_back(b, e);
    cs[b].push_back(v);
    cs[e].push_back(v);
  }
  std::cin >> Q;
  for (int i = 1; i <= Q; ++i) {
    std::cin >> xs[i] >> ys[i];
    qs[xs[i]].push_back(i);
  }
  for (int i = 1; i <= m; ++i)
    if (es[i].size() >= BLO) {
      int idx = 0;
      addcol(i);
      for (int j = 1; j <= n; ++j)
        if (!bel[j]) bfs(j, ++idx);
      for (int j = 1; j <= Q; ++j) ansl[j] += bel[xs[j]] == bel[ys[j]];
      delcol(i);
      memset(bel, 0, sizeof bel);
      bak = 0;
    }
  memset(ta, 0, sizeof ta);
  for (int i = 1; i <= n; ++i) {
    std::sort(cs[i].begin(), cs[i].end());
    cs[i].erase(std::unique(cs[i].begin(), cs[i].end()), cs[i].end());
    for (auto t : cs[i])
      if (es[t].size() < BLO) {
        addcol(t);
        bfs(i, 1);
        delcol(t);
      }
    for (auto t : qs[i]) ansl[t] += ta[ys[t]];
    for (int j = 1; j <= bak; ++j) ta[li[j]] = 0;
    bak = 0;
  }
  for (int i = 1; i <= Q; ++i) std::cout << ansl[i] << '\n';
  return 0;
}
