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;
const long long MOD = 1e9 + 7;
const long long INF = 1e9;
const long long MAXN = 100010;
const long long BSIZ = 300;
int N, E, a, b, c, Q;
vector<pair<long long, long long> > col[MAXN];
vector<long long> V[MAXN];
map<pair<long long, long long>, int> M;
int p[MAXN];
int par(int x) { return (p[x] == x) ? x : p[x] = par(p[x]); }
int res[MAXN];
vector<pair<long long, long long> > queries;
int ans[MAXN];
int vis[MAXN];
vector<long long> cur;
void dfs(int x) {
  vis[x] = 1;
  cur.emplace_back(x);
  for (auto t : V[x])
    if (!vis[t]) {
      dfs(t);
    }
}
int main() {
  cin >> N >> E;
  for (int i = 1; i <= E; ++i) {
    cin >> a >> b >> c;
    col[c].emplace_back(a, b);
  }
  cin >> Q;
  for (int i = 0; i < Q; ++i) {
    cin >> a >> b;
    queries.emplace_back(a, b);
  }
  for (int i = 1; i <= E; ++i) {
    if ((long long)col[i].size() <= BSIZ) continue;
    for (int j = 1; j <= N; ++j) p[j] = j;
    for (auto e : col[i]) {
      int a = par(e.first);
      int b = par(e.second);
      if (a != b) p[a] = b;
    }
    for (int i = 0; i < Q; ++i) {
      if (par(queries[i].first) == par(queries[i].second)) ++ans[i];
    }
  }
  for (int i = 1; i <= E; ++i) {
    if ((long long)col[i].size() > BSIZ) continue;
    set<int> nodes;
    for (auto e : col[i]) {
      V[e.first].emplace_back(e.second);
      V[e.second].emplace_back(e.first);
      nodes.insert(e.first);
      nodes.insert(e.second);
    }
    for (auto i : nodes) vis[i] = 0;
    for (auto i : nodes)
      if (!vis[i]) {
        dfs(i);
        for (auto i : cur)
          for (auto j : cur) {
            if (i < j) M[make_pair(i, j)]++;
          }
        cur.clear();
      }
    for (auto i : nodes) V[i].clear();
  }
  for (int i = 0; i < Q; ++i) {
    int a = queries[i].first;
    int b = queries[i].second;
    ans[i] += M[make_pair(min(a, b), max(a, b))];
    cout << ans[i] << '\n';
  }
}
