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 MAXN = 1e5 + 5;
struct timearray {
  int gt = 1;
  int val[MAXN];
  int dhgdg[MAXN];
  timearray() { memset(dhgdg, 0, sizeof(dhgdg)); }
  void clear() { gt++; }
  int get(int i) {
    if (dhgdg[i] < gt) return -1;
    return val[i];
  }
  void set(int i, int x) {
    val[i] = x;
    dhgdg[i] = gt;
  }
};
unordered_map<int, int> qs[MAXN];
int ansq[MAXN];
int ta[MAXN];
pair<int, int> cq[MAXN];
map<pair<int, int>, int> la;
int cnt[MAXN];
set<int> big;
int n, m;
int cut;
vector<pair<int, int> > e[MAXN];
map<int, int> id;
int cid = 0;
int q;
int stk[MAXN];
int ptr = 0;
timearray p, rnk, used;
int find_set(int v) {
  if (p.get(v) == -1) {
    p.set(v, v);
    return v;
  }
  if (p.get(v) == v)
    return v;
  else {
    int x = find_set(p.get(v));
    p.set(v, x);
    return x;
  }
}
void unite(int v, int u) {
  v = find_set(v);
  u = find_set(u);
  if (v == u) return;
  if (rnk.get(v) == -1) rnk.set(v, 0);
  if (rnk.get(u) == -1) rnk.set(u, 0);
  if (rnk.get(v) > rnk.get(u)) swap(v, u);
  p.set(v, u);
  if (rnk.get(v) == rnk.get(u)) rnk.set(u, rnk.get(u) + 1);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  memset(cnt, 0, sizeof(cnt));
  memset(ta, 0, sizeof(ta));
  memset(ansq, 0, sizeof(ansq));
  scanf("%d%d", &n, &m);
  for (auto i = 0; i != n; i++) qs[i].max_load_factor(0.25);
  cut = (int)sqrt((long double)m) / 4;
  cut = max(1, cut);
  for (auto i = 0; i != m; i++) {
    int v, u, c;
    scanf("%d%d%d", &v, &u, &c);
    v--;
    u--;
    if (!id.count(c)) id[c] = cid++;
    int nc = id[c];
    e[nc].push_back(make_pair(v, u));
    cnt[nc]++;
  }
  scanf("%d", &q);
  for (auto i = 0; i != q; i++) {
    int v, u;
    scanf("%d%d", &v, &u);
    v--;
    u--;
    if (v > u) swap(v, u);
    cq[i] = make_pair(v, u);
    if (la.count(make_pair(v, u))) continue;
    qs[v][u] = i;
    la[make_pair(v, u)] = i;
  }
  for (auto cc : id) {
    int c = cc.second;
    if (cnt[c] < cut) {
      ptr = 0;
      p.clear();
      rnk.clear();
      used.clear();
      for (auto ce : e[c]) {
        int v = ce.first, u = ce.second;
        unite(v, u);
        if (used.get(v) == -1) {
          used.set(v, 0);
          stk[ptr++] = v;
        }
        if (used.get(u) == -1) {
          used.set(u, 0);
          stk[ptr++] = u;
        }
      }
      for (auto i = 0; i != ptr; i++) {
        for (auto j = i + 1; j != ptr; j++) {
          int v = stk[i], u = stk[j];
          if (v > u) swap(v, u);
          if (find_set(v) != find_set(u)) continue;
          if (qs[v].count(u)) ansq[qs[v][u]]++;
        }
      }
    } else {
      p.clear();
      rnk.clear();
      used.clear();
      for (auto ce : e[c]) {
        int v = ce.first, u = ce.second;
        unite(v, u);
      }
      for (auto i = 0; i != q; i++) {
        if (find_set(cq[i].first) == find_set(cq[i].second)) ta[i]++;
      }
    }
  }
  for (auto i = 0; i != q; i++) {
    ta[i] += ansq[la[cq[i]]];
    printf("%d\n", ta[i]);
  }
  return 0;
}
