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;
int n, m, d[100005], s[100005], ans[100005], cnt[100005], t, nq;
vector<int> a[100005], b[100005], e[100005], q[100005], id[100005];
bool v[100005];
int f(int x) { return x == s[x] ? x : s[x] = f(s[x]); }
void go(int x) {
  if (d[x] > t) return;
  for (int i = (0); i < (q[x].size()); i++) ans[id[x][i]] += f(x) == f(q[x][i]);
}
void dfs(int x) {
  if (v[x]) return;
  v[x] = 1;
  cnt[x]++;
  for (int i = (0); i < (e[x].size()); i++) dfs(e[x][i]);
}
void dfs2(int x) {
  if (!v[x]) return;
  v[x] = 0;
  for (int i = (0); i < (e[x].size()); i++) dfs2(e[x][i]);
}
int main() {
  scanf("%d %d", &n, &m);
  for (int i = (0); i < (m); i++) {
    int x, y, z;
    scanf("%d %d %d", &x, &y, &z);
    d[x]++;
    d[y]++;
    a[z].push_back(x);
    b[z].push_back(y);
  }
  t = m * 2 / 305;
  scanf("%d", &nq);
  for (int i = (0); i < (nq); i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    if (d[x] < d[y]) swap(x, y);
    if (d[x] > t) {
      q[x].push_back(y);
      id[x].push_back(i);
    } else {
      q[y].push_back(x);
      id[y].push_back(i);
    }
  }
  for (int i = (1); i <= (n); i++) s[i] = i;
  for (int i = (1); i <= (m); i++) {
    for (int j = (0); j < (a[i].size()); j++) s[f(a[i][j])] = f(b[i][j]);
    for (int j = (0); j < (a[i].size()); j++) {
      if (!v[a[i][j]] && d[a[i][j]] <= t)
        for (int k = (0); k < (q[a[i][j]].size()); k++)
          ans[id[a[i][j]][k]] += f(a[i][j]) == f(q[a[i][j]][k]);
      if (!v[b[i][j]] && d[b[i][j]] <= t)
        for (int k = (0); k < (q[b[i][j]].size()); k++)
          ans[id[b[i][j]][k]] += f(b[i][j]) == f(q[b[i][j]][k]);
      v[a[i][j]] = v[b[i][j]] = 1;
    }
    for (int j = (0); j < (a[i].size()); j++) {
      v[a[i][j]] = v[b[i][j]] = 0;
      s[a[i][j]] = a[i][j];
      s[b[i][j]] = b[i][j];
    }
  }
  for (int z = (1); z <= (n); z++)
    if (d[z] > t) {
      for (int i = (1); i <= (n); i++) cnt[i] = 0;
      for (int i = (1); i <= (m); i++) {
        for (int j = (0); j < (a[i].size()); j++) {
          e[a[i][j]].push_back(b[i][j]);
          e[b[i][j]].push_back(a[i][j]);
        }
        dfs(z);
        dfs2(z);
        for (int j = (0); j < (a[i].size()); j++) {
          e[a[i][j]].clear();
          e[b[i][j]].clear();
        }
      }
      for (int i = (0); i < (q[z].size()); i++) ans[id[z][i]] = cnt[q[z][i]];
    }
  for (int i = (0); i < (nq); i++) printf("%d\n", ans[i]);
  scanf("\n");
}
