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>
#pragma GCC optimize("Ofast", "unroll-loops")
using namespace std;
const int inf = numeric_limits<int>::max() / 2;
const long double eps = 1e-9;
const long double pi = acos(-1);
inline void solve(), read();
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  read();
  solve();
  return 0;
}
const int MAXN = 1e5 + 1;
const int MAXM = 1e5 + 1;
const int MAXC = 450;
struct dsu {
  int n;
  int t[MAXN], rk[MAXN];
  dsu() {}
  dsu(int n_) {
    n = n_;
    iota(t, t + n, 0);
    fill(rk, rk + n, 0);
  }
  int find(int v) {
    if (v == t[v]) {
      return v;
    }
    return t[v] = find(t[v]);
  }
  void join(int v, int u) {
    v = find(v), u = find(u);
    if (v != u) {
      if (rk[v] < rk[u]) {
        swap(v, u);
      }
      t[u] = v;
      if (rk[v] == rk[u]) {
        ++rk[v];
      }
    }
  }
};
int n, m, q;
dsu d;
vector<pair<int, int> > es[MAXM];
vector<int> temp[MAXN];
vector<vector<int> > comp;
int used[MAXN];
vector<int> a[MAXN];
int large_id[MAXN];
vector<int> large;
int large_ans[MAXC][MAXN];
inline void solve() {
  d = dsu(n);
  for (int c = 0; c < m; c++) {
    for (pair<int, int> p : es[c]) {
      d.join(p.first, p.second);
    }
    for (pair<int, int> p : es[c]) {
      int a, b;
      tie(a, b) = p;
      if (!used[a]) {
        temp[d.find(a)].push_back(a);
        used[a] = 1;
      }
      if (!used[b]) {
        temp[d.find(b)].push_back(b);
        used[b] = 1;
      }
    }
    for (pair<int, int> p : es[c]) {
      int a, b;
      tie(a, b) = p;
      if ((int)((temp[a]).size()) > 0) {
        comp.push_back(temp[a]);
        temp[a].clear();
      }
      if ((int)((temp[b]).size()) > 0) {
        comp.push_back(temp[b]);
        temp[b].clear();
      }
      used[a] = used[b] = 0;
      d.rk[a] = d.rk[b] = 0;
      d.t[a] = a, d.t[b] = b;
    }
  }
  for (int i = 0; i < (int)((comp).size()); i++) {
    for (int j = 0; j < (int)((comp[i]).size()); j++) {
      a[comp[i][j]].push_back(i);
    }
  }
  for (int i = 0; i < n; i++) {
    if ((int)((a[i]).size()) > MAXC) {
      large.push_back(i);
      large_id[i] = (int)((large).size()) - 1;
    } else {
      large_id[i] = -1;
    }
  }
  for (int i = 0; i < (int)((large).size()); i++) {
    int v = large[i];
    for (int c : a[v]) {
      for (int u : comp[c]) {
        ++large_ans[i][u];
      }
    }
  }
  cin >> q;
  for (int i = 0; i < q; i++) {
    int v, u;
    cin >> v >> u;
    --v, --u;
    int ans = 0;
    if (large_id[v] == -1) {
      swap(v, u);
    }
    if (large_id[v] != -1) {
      ans = large_ans[large_id[v]][u];
    } else {
      int i = 0, j = 0;
      while (i < (int)((a[v]).size()) && j < (int)((a[u]).size())) {
        if (a[v][i] == a[u][j]) {
          ++ans;
          ++i, ++j;
        } else if (a[v][i] < a[u][j]) {
          ++i;
        } else {
          ++j;
        }
      }
    }
    cout << ans << "\n";
  }
}
inline void read() {
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    int v, u, c;
    cin >> v >> u >> c;
    --v, --u, --c;
    es[c].push_back({v, u});
  }
}
