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 = 1e5 + 10, B = 650;
int n, m, first[N], second[N], f[N];
struct edge {
  int a, b, c;
} e[N];
inline bool operator<(const edge &a, const edge &b) { return a.c < b.c; }
inline int find(int first) {
  return first == f[first] ? first : f[first] = find(f[first]);
}
map<int, int> d[N];
int ans[N];
vector<int> nd;
int main() {
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= m; i++) scanf("%d%d%d", &e[i].a, &e[i].b, &e[i].c);
  sort(e + 1, e + m + 1);
  int q;
  scanf("%d", &q);
  for (int i = 1; i <= q; i++) {
    scanf("%d%d", first + i, second + i);
    if (first[i] > second[i]) swap(first[i], second[i]);
    d[first[i]][second[i]] = 0;
  }
  for (int i = 1; i <= n; i++) f[i] = i;
  for (int l = 1, r; l <= m; l = r + 1) {
    r = l;
    while (r < m && e[r + 1].c == e[r].c) r++;
    if (r - l + 1 > B) {
      for (int i = l; i <= r; i++) {
        int fa = find(e[i].a), fb = find(e[i].b);
        f[fa] = fb;
      }
      for (int i = 1; i <= q; i++) ans[i] += find(first[i]) == find(second[i]);
      for (int i = l; i <= r; i++) f[e[i].a] = e[i].a, f[e[i].b] = e[i].b;
    } else {
      nd.clear();
      for (int i = l; i <= r; i++) {
        nd.push_back(e[i].a), nd.push_back(e[i].b);
        int fa = find(e[i].a), fb = find(e[i].b);
        f[fa] = fb;
      }
      sort(nd.begin(), nd.end());
      vector<int>::iterator it = unique(nd.begin(), nd.end());
      nd.erase(it, nd.end());
      int len = nd.size();
      for (int i = 0; i < len; i++)
        for (int j = i + 1; j <= len - 1; j++)
          if (find(nd[i]) == find(nd[j]) &&
              d[nd[i]].find(nd[j]) != d[nd[i]].end())
            d[nd[i]][nd[j]]++;
      for (int i = 0; i < len; i++) f[nd[i]] = nd[i];
    }
  }
  for (int i = 1; i <= q; i++) ans[i] += d[first[i]][second[i]];
  for (int i = 1; i <= q; i++) printf("%d\n", ans[i]);
  return 0;
}
