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;
template <typename T>
T in() {
  char ch;
  T n = 0;
  bool ng = false;
  while (1) {
    ch = getchar();
    if (ch == '-') {
      ng = true;
      ch = getchar();
      break;
    }
    if (ch >= '0' && ch <= '9') break;
  }
  while (1) {
    n = n * 10 + (ch - '0');
    ch = getchar();
    if (ch < '0' || ch > '9') break;
  }
  return (ng ? -n : n);
}
template <typename T>
inline T POW(T B, T P) {
  if (P == 0) return 1;
  if (P & 1)
    return B * POW(B, P - 1);
  else
    return (POW(B, P / 2) * POW(B, P / 2));
}
template <typename T>
inline T Gcd(T a, T b) {
  if (a < 0) return Gcd(-a, b);
  if (b < 0) return Gcd(a, -b);
  return (b == 0) ? a : Gcd(b, a % b);
}
template <typename T>
inline T Lcm(T a, T b) {
  if (a < 0) return Lcm(-a, b);
  if (b < 0) return Lcm(a, -b);
  return a * (b / Gcd(a, b));
}
long long Bigmod(long long base, long long power, long long MOD) {
  long long ret = 1;
  while (power) {
    if (power & 1) ret = (ret * base) % MOD;
    base = (base * base) % MOD;
    power >>= 1;
  }
  return ret;
}
bool isVowel(char ch) {
  ch = toupper(ch);
  if (ch == 'A' || ch == 'U' || ch == 'I' || ch == 'O' || ch == 'E')
    return true;
  return false;
}
template <typename T>
long long int isLeft(T a, T b, T c) {
  return (a.x - b.x) * (b.y - c.y) - (b.x - c.x) * (a.y - b.y);
}
long long ModInverse(long long number, long long MOD) {
  return Bigmod(number, MOD - 2, MOD);
}
bool isConst(char ch) {
  if (isalpha(ch) && !isVowel(ch)) return true;
  return false;
}
int toInt(string s) {
  int sm;
  stringstream second(s);
  second >> sm;
  return sm;
}
const int lim = 350;
bool ache[100005][lim + 10];
vector<pair<int, int> > A[100005];
vector<int> B[100005];
vector<int> C[100005];
int cmp;
int par[100005];
int vis[100005], KS;
int find(int u) {
  if (par[u] == u) return u;
  return par[u] = find(par[u]);
}
vector<int> aa[100005];
void lol(int u) {
  vis[u] = KS;
  B[cmp].push_back(u);
  for (int i = 0; i < aa[u].size(); i++) {
    int v = aa[u][i];
    if (vis[v] == KS) continue;
    lol(v);
  }
}
int main() {
  int n, m;
  n = in<int>(), m = in<int>();
  int mxc = 0;
  for (int i = 0; i < m; i++) {
    int a, b, c;
    a = in<int>(), b = in<int>(), c = in<int>();
    A[c].push_back(make_pair(a, b));
    mxc = max(mxc, c);
  }
  for (int i = 1; i < n + 1; i++) par[i] = i;
  for (int i = 1; i <= mxc; i++) {
    if (A[i].size()) {
      for (int j = 0; j < A[i].size(); j++) {
        pair<int, int> tp = A[i][j];
        int a = tp.first, b = tp.second;
        int pa = find(a);
        int pb = find(b);
        if (pa == pb) continue;
        par[pa] = pb;
        aa[pb].push_back(pa);
        aa[pa].push_back(pb);
      }
      ++KS;
      for (int j = 0; j < A[i].size(); j++) {
        pair<int, int> tp = A[i][j];
        int a = tp.first, b = tp.second;
        if (vis[a] != KS) {
          ++cmp;
          lol(a);
        }
        if (vis[b] != KS) {
          ++cmp;
          lol(b);
        }
        aa[a].clear();
        aa[b].clear();
        par[a] = a;
        par[b] = b;
      }
    }
  }
  int now = 0;
  for (int i = 1; i < cmp + 1; i++) {
    int ln = B[i].size();
    if (ln <= lim) {
      for (int j = 0; j < ln; j++) {
        for (int k = j + 1; k < ln; k++) {
          int a = B[i][j];
          int b = B[i][k];
          if (a > b) swap(a, b);
          C[a].push_back(b);
        }
      }
    } else {
      ++now;
      for (int j = 0; j < ln; j++) {
        int v = B[i][j];
        ache[v][now] = 1;
      }
    }
  }
  for (int i = 1; i < n + 1; i++) sort(C[i].begin(), C[i].end());
  int q;
  q = in<int>();
  while (q--) {
    int a, b;
    a = in<int>(), b = in<int>();
    if (a > b) swap(a, b);
    int ans = upper_bound(C[a].begin(), C[a].end(), b) -
              lower_bound(C[a].begin(), C[a].end(), b);
    for (int i = 1; i <= now; i++) {
      if (ache[a][i] && ache[b][i]) ans++;
    }
    printf("%d\n", ans);
  }
  return 0;
}
