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>
inline int getInt() {
  int s;
  scanf("%d", &s);
  return s;
}
using namespace std;
class UnionFind {
 private:
  int getId(int i) const {
    if (i == id[i]) return i;
    return id[i] = getId(id[i]);
  }

 public:
  mutable vector<int> id;
  UnionFind(int size = 0) { init(size); }
  ~UnionFind() {}
  void init(int size) {
    id = vector<int>(size);
    for (int i = 0; i < size; i++) id[i] = i;
  }
  void unite(int i, int j) {
    int next = min(getId(i), getId(j));
    id[getId(i)] = id[getId(j)] = next;
  }
  int operator[](int i) const { return getId(i); }
  int count() const {
    set<int> s;
    for (int i = 0; i < (int)id.size(); i++) s.insert(getId(i));
    return s.size();
  }
};
vector<pair<int, int> > g[100000];
vector<int> qs[100000];
vector<int> buff[100000];
int qa[100000];
int qb[100000];
int ans[100000];
int cnt[100000];
int main() {
  const int n = getInt();
  const int m = getInt();
  for (int i = 0; i < (int)(m); i++) {
    const int a = getInt() - 1;
    const int b = getInt() - 1;
    const int c = getInt() - 1;
    cnt[a]++;
    cnt[b]++;
    g[c].push_back(make_pair(a, b));
  }
  const int q = getInt();
  set<pair<int, int> > s;
  for (int i = 0; i < (int)(q); i++) {
    qa[i] = getInt() - 1;
    qb[i] = getInt() - 1;
    const int mn = min(qa[i], qb[i]);
    const int mx = max(qa[i], qb[i]);
    if (s.count(make_pair(mn, mx))) continue;
    s.insert(make_pair(mn, mx));
    if (cnt[qa[i]] < cnt[qb[i]])
      qs[qa[i]].push_back(i);
    else
      qs[qb[i]].push_back(i);
  }
  UnionFind uf(n);
  for (int c = 0; c < (int)(m); c++)
    if (g[c].size()) {
      set<int> used;
      for (int i = 0; i < (int)(g[c].size()); i++) {
        const int a = g[c][i].first;
        const int b = g[c][i].second;
        uf.unite(a, b);
        used.insert(a);
        used.insert(b);
      }
      for (int i : used) {
        if (uf[i] == i) {
          buff[i].clear();
        }
      }
      for (int i : used) {
        buff[uf[i]].push_back(i);
      }
      for (int i : used) {
        if (uf[i] == i) {
          const vector<int> &v = buff[i];
          for (int j : v) {
            const vector<int> &qq = qs[j];
            for (int p : qq) {
              const int aa = qa[p];
              const int bb = qb[p];
              if (uf.id[aa] == uf.id[bb]) ans[p]++;
            }
          }
        }
      }
      for (int i : used) {
        uf.id[i] = i;
      }
    }
  map<pair<int, int>, int> memo;
  for (int i = 0; i < (int)(q); i++) {
    const int mn = min(qa[i], qb[i]);
    const int mx = max(qa[i], qb[i]);
    if (memo.count(make_pair(mn, mx))) ans[i] = memo[make_pair(mn, mx)];
    memo[make_pair(mn, mx)] = ans[i];
    printf("%d\n", ans[i]);
  }
  return 0;
}
