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 inf_int = 1e9 + 100;
const long long inf_ll = 1e18;
const double pi = 3.1415926535898;
bool debug = 0;
const int MAXN = 3e5 + 100;
const int LOG = 21;
const int mod = 1e9 + 7;
const int MX = (1e6 + 100);
template <class T1, class T2>
std::ostream &operator<<(std::ostream &out, const std::pair<T1, T2> &rhs) {
  out << "( " << rhs.first << " , " << rhs.second << " )";
  return out;
}
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string &s) { return '"' + s + '"'; }
string to_string(const char *s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto &x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
vector<pair<int, int> > clr[MAXN];
int timer;
int used[MAXN];
vector<int> comp;
vector<int> g[MAXN];
void dfs(int v) {
  if (used[v] == timer) {
    return;
  }
  used[v] = timer;
  comp.push_back(v);
  for (int to : g[v]) {
    dfs(to);
  }
}
vector<int> vals[MAXN];
int clz(int N) { return N ? 32 - __builtin_clz(N) : -1e9; }
int solve(const vector<int> &a, const vector<int> &b) {
  int ans = 0;
  if ((int(a.size())) >= 10 && (int(a.size())) + (int(b.size())) <=
                                   (int(a.size())) * clz((int(b.size())))) {
    int i1 = 0, i2 = 0;
    while (i1 < (int(a.size())) && i2 < (int(b.size()))) {
      if (a[i1] == b[i2]) {
        i1++;
        i2++;
        ans++;
      } else if (a[i1] > b[i2])
        i2++;
      else
        i1++;
    }
    return ans;
  }
  assert((int(a.size())) <= (int(b.size())));
  for (auto x : a) {
    auto it = lower_bound(b.begin(), b.end(), x);
    if (it != b.end() && *it == x) {
      ans++;
    }
  }
  return ans;
}
int calc(vector<int> &a, vector<int> &b) {
  if ((int(a.size())) < (int(b.size()))) {
    return solve(a, b);
  }
  return solve(b, a);
}
void solve() {
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= m; ++i) {
    int a, b, c;
    cin >> a >> b >> c;
    clr[c].push_back({a, b});
  }
  int id = 0;
  for (int i = 1; i <= m; ++i) {
    vector<int> vers;
    for (auto x : clr[i]) {
      vers.push_back(x.first);
      vers.push_back(x.second);
    }
    for (auto v : vers) {
      g[v].clear();
    }
    for (auto x : clr[i]) {
      g[x.first].push_back(x.second);
      g[x.second].push_back(x.first);
    }
    timer++;
    for (auto v : vers) {
      if (used[v] != timer) {
        comp.clear();
        dfs(v);
        id++;
        for (int v : comp) {
          vals[v].push_back(id);
        }
      }
    }
  }
  int q;
  cin >> q;
  map<pair<int, int>, int> make_pair;
  for (int i = 1; i <= q; ++i) {
    int a, b;
    cin >> a >> b;
    if (make_pair.count({a, b})) {
      cout << make_pair[{a, b}] << "\n";
      continue;
    }
    int res = calc(vals[a], vals[b]);
    make_pair[{a, b}] = make_pair[{b, a}] = res;
    cout << res << "\n";
  }
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cout.setf(ios::fixed);
  cout.precision(15);
  int t = 1;
  while (t--) solve();
  42;
}
