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 <class T>
inline bool tension(T &a, T b) {
  if (b < a) {
    a = b;
    return true;
  }
  return false;
}
template <class T>
inline bool relax(T &a, T b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}
int n, m, q;
struct NODE {
  int v;
  NODE *next;
} mem[400009], *mp = mem, *adj[400009];
struct EDGE {
  int u, v, c;
  bool operator<(const EDGE &b) const { return c < b.c; }
} edge[400009];
int lastacs[400009], act;
map<pair<int, int>, int> mm;
int ans[400009];
int a[400009], b[400009];
void work(int p, int times) {
  static int que[400009];
  int head = 0, tail = 0;
  que[++tail] = p;
  while (head != tail) {
    int now = que[++head];
    lastacs[now] = times;
    for (NODE *o = adj[now]; o; o = o->next)
      if (lastacs[o->v] != times) {
        lastacs[o->v] = times;
        que[++tail] = o->v;
      }
  }
  if (tail * tail <= n) {
    int i, j;
    for (i = 1; i <= tail; i++) {
      for (j = i + 1; j <= tail; j++) {
        int u = que[i], v = que[j];
        if (u > v) swap(u, v);
        mm[make_pair(u, v)]++;
      }
    }
  } else {
    int i;
    for (i = 1; i <= q; i++) {
      if (lastacs[a[i]] == lastacs[b[i]] && lastacs[a[i]] == times) {
        ans[i]++;
      }
    }
  }
}
int main() {
  scanf("%d %d", &n, &m);
  int i, j;
  for (i = 1; i <= m; i++) {
    scanf("%d %d %d", &edge[i].u, &edge[i].v, &edge[i].c);
  }
  sort(edge + 1, edge + m + 1);
  scanf("%d", &q);
  for (i = 1; i <= q; i++) {
    scanf("%d %d", a + i, b + i);
    if (a[i] > b[i]) swap(a[i], b[i]);
  }
  for (i = 1; i <= m; i = j) {
    static int que[400009];
    int tail = 0;
    for (j = i; j <= m && edge[j].c == edge[i].c; j++) {
      mp++;
      mp->v = edge[j].v;
      mp->next = adj[edge[j].u];
      adj[edge[j].u] = mp;
      mp++;
      mp->v = edge[j].u;
      mp->next = adj[edge[j].v];
      adj[edge[j].v] = mp;
      que[++tail] = edge[j].u;
      que[++tail] = edge[j].v;
    }
    int k;
    int lact = act;
    for (k = 1; k <= tail; k++) {
      if (lastacs[que[k]] <= lact) {
        act++;
        work(que[k], act);
      }
    }
    for (k = 1; k <= tail; k++) adj[que[k]] = 0;
  }
  for (i = 1; i <= q; i++) {
    printf("%d\n", mm[make_pair(a[i], b[i])] + ans[i]);
  }
  return 0;
}
