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 int nsz = 1e5, bsz = 400;
bool vis[nsz + 5];
int n, m, q, sz, to[nsz + 5], tmp[bsz + 5], ans;
vector<int> res[nsz + 5];
vector<pair<int, int>> e[nsz + 5];
struct graph {
  int sz, fm[nsz + 5], nxt[2 * bsz + 5], to[2 * bsz + 5];
  void inline clear() {
    fill(nxt, nxt + sz + 1, 0);
    fill(to, to + sz + 1, 0);
    sz = 0;
  }
  void inline connect(int u, int v) {
    nxt[++sz] = fm[u];
    fm[u] = sz;
    to[sz] = v;
  }
};
graph g;
struct union_find {
  int pr[nsz + 5];
  void inline init() {
    for (int i = 1; i <= n; ++i) {
      pr[i] = i;
    }
  }
  int qry(int u) { return pr[u] == u ? u : pr[u] = qry(pr[u]); }
  bool inline unite(int u, int v) {
    int pu = qry(u), pv = qry(v);
    if (pu == pv) return 0;
    pr[pv] = pu;
    return 1;
  }
};
union_find uf[bsz + 5];
void inline work(int c) {
  int s = 0, tmp[bsz + 5];
  queue<int> q;
  set<int> est;
  unordered_map<int, bool> vis;
  g.clear();
  for (int i = 0; i < e[c].size(); ++i) {
    int u = e[c][i].first, v = e[c][i].second;
    g.connect(u, v);
    g.connect(v, u);
    est.insert(u);
    est.insert(v);
  }
  for (__typeof(est.begin()) it = est.begin(); it != est.end(); ++it) {
    int u = *it;
    if (vis[u]) continue;
    s = 0;
    q.push(u);
    vis[u] = 1;
    for (; q.size();) {
      int u = q.front();
      q.pop();
      tmp[++s] = u;
      for (int i = g.fm[u]; i; i = g.nxt[i]) {
        int v = g.to[i];
        if (vis[v]) continue;
        q.push(v);
        vis[v] = 1;
      }
    }
    for (int i = 1; i <= s; ++i) {
      int u = tmp[i];
      for (int j = 1; j <= s; ++j) {
        int v = tmp[j];
        if (u == v) continue;
        res[u].push_back(v);
      }
    }
  }
  for (__typeof(est.begin()) it = est.begin(); it != est.end(); ++it) {
    g.fm[*it] = 0;
  }
}
int inline read() {
  int res = 0;
  char c = getchar();
  for (; !isdigit(c); c = getchar())
    ;
  for (; isdigit(c); res *= 10, res += c ^ 48, c = getchar())
    ;
  return res;
}
void inline writeln(int a) {
  int s = 0, d[10] = {0};
  for (; a; d[s++] = a % 10, a /= 10)
    ;
  for (s = s ? s : 1; s; putchar(d[--s] + 48))
    ;
  putchar('\n');
}
int main() {
  n = read(), m = read();
  for (int i = 1; i <= m; ++i) {
    int u = read(), v = read(), c = read();
    e[c].push_back(make_pair(u, v));
  }
  for (int c = 1; c <= m; ++c) {
    if (e[c].size() && e[c].size() <= bsz) {
      work(c);
    } else if (e[c].size() > bsz) {
      to[c] = ++sz;
      uf[sz].init();
      for (int i = 0; i < e[c].size(); ++i) {
        int u = e[c][i].first, v = e[c][i].second;
        uf[sz].unite(u, v);
      }
    }
  }
  for (int u = 1; u <= n; ++u) {
    sort(res[u].begin(), res[u].end());
  }
  q = read();
  for (int i = 1; i <= q; ++i) {
    int u = read(), v = read();
    ans = (int)(upper_bound(res[u].begin(), res[u].end(), v) -
                lower_bound(res[u].begin(), res[u].end(), v));
    for (int i = 1; i <= sz; ++i) {
      ans += uf[i].qry(u) == uf[i].qry(v);
    }
    writeln(ans);
  }
}
