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 N = 100 + 2;
const int MOD = 1 << 30;
const double pi = acos(-1);
struct line {
  double a, b, c;
};
struct point {
  double x, y;
};
void pointsToLine(point p1, point p2, line &l) {
  if (fabs(p1.x - p2.x) < 1e-2) {
    l.a = 1.0;
    l.b = 0.0;
    l.c = -p1.x;
  } else {
    l.a = -(double)(p1.y - p2.y) / (p1.x - p2.x);
    l.b = 1.0;
    l.c = -(double)(l.a * p1.x) - p1.y;
  }
}
bool areParallel(line l1, line l2) {
  return ((fabs(l1.a - l2.a) < 1e-2) && (fabs(l2.b - l2.b) < 1e-2));
}
bool areSame(line l1, line l2) {
  return (areParallel(l1, l2) && (fabs(l1.c - l2.c) < 1e-2));
}
bool areIntersect(line l1, line l2, point &p) {
  if (areParallel(l1, l2)) return false;
  p.x = (l2.b * l1.c - l1.b * l2.c) / (l2.a * l1.b - l1.a * l2.b);
  if (fabs(l1.b) > 1e-2)
    p.y = -(l1.a * p.x + l1.c);
  else
    p.y = -(l2.a * p.x + l2.c);
  return true;
}
vector<pair<int, int> > AdjList[N];
int n, m;
int vis[N];
void dfs(int u, int c) {
  vis[u] = true;
  for (int i = 0; i < (int)AdjList[u].size(); ++i) {
    pair<int, int> v = AdjList[u][i];
    if (!vis[v.first]) {
      if (v.second == c) dfs(v.first, v.second);
    }
  }
}
void solve() {
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    AdjList[u].push_back({v, w});
    AdjList[v].push_back({u, w});
  }
  int q;
  cin >> q;
  while (q--) {
    int u, v;
    cin >> u >> v;
    int ans = 0;
    for (int i = 1; i <= m; ++i) {
      memset(vis, false, sizeof vis);
      dfs(u, i);
      if (vis[v]) ans++;
    }
    cout << ans << '\n';
  }
}
int main(void) {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int tc = 1;
  while (tc--) solve();
}
