Problem: Easy and hard versions are actually different problems, so we advise you to read both statements carefully.

You are given a weighted rooted tree, vertex 1 is the root of this tree.

A tree is a connected graph without cycles. A rooted tree has a special vertex called the root. A parent of a vertex v is the last different from v vertex on the path from the root to the vertex v. Children of vertex v are all vertices for which v is the parent. A vertex is a leaf if it has no children. The weighted tree is such a tree that each edge of this tree has some weight.

The weight of the path is the sum of edges weights on this path. The weight of the path from the vertex to itself is 0.

You can make a sequence of zero or more moves. On each move, you select an edge and divide its weight by 2 rounding down. More formally, during one move, you choose some edge i and divide its weight by 2 rounding down (w_i := \left⌊(w_i)/(2)\right⌋).

Your task is to find the minimum number of moves required to make the sum of weights of paths from the root to each leaf at most S. In other words, if w(i, j) is the weight of the path from the vertex i to the vertex j, then you have to make ∑_{v ∈ leaves} w(root, v) ≤ S, where leaves is the list of all leaves.

You have to answer t independent test cases.

Input

The first line of the input contains one integer t (1 ≤ t ≤ 2 ⋅ 10^4) — the number of test cases. Then t test cases follow.

The first line of the test case contains two integers n and S (2 ≤ n ≤ 10^5; 1 ≤ S ≤ 10^{16}) — the number of vertices in the tree and the maximum possible sum of weights you have to obtain. The next n-1 lines describe edges of the tree. The edge i is described as three integers v_i, u_i and w_i (1 ≤ v_i, u_i ≤ n; 1 ≤ w_i ≤ 10^6), where v_i and u_i are vertices the edge i connects and w_i is the weight of this edge.

It is guaranteed that the sum of n does not exceed 10^5 (∑ n ≤ 10^5).

Output

For each test case, print the answer: the minimum number of moves required to make the sum of weights of paths from the root to each leaf at most S.

Example

Input


3
3 20
2 1 8
3 1 7
5 50
1 3 100
1 5 10
2 3 123
5 4 55
2 100
1 2 409


Output


0
8
3

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
inline long long modpow(long long x, long long y, long long m = 1000000007ll) {
  long long res = 1;
  while (y) {
    if (y & 1) {
      res *= x;
      res %= m;
    }
    x = x * x % m;
    y /= 2;
  }
  return res;
}
long long mypow(long long x, long long y) {
  long long res = 1;
  while (y) {
    if (y % 2) {
      res *= x;
    }
    x = x * x;
    y /= 2;
  }
  return res;
}
bool prime(long long x) {
  if (!x || x == 1) {
    return false;
  }
  for (long long i = 2; i * i <= x; i++) {
    if (!(x % i)) {
      return false;
    }
  }
  return true;
}
inline long long gcd(long long x, long long y) {
  if (!y) {
    return x;
  }
  return gcd(y, x % y);
}
long long keta(long long x) {
  long long ans = 0;
  while (x) {
    x /= 10;
    ans++;
  }
  return ans;
}
long long bitketa(long long x) {
  long long ans = 0;
  while (x) {
    x >>= 1;
    ans++;
  }
  return ans;
}
long long ketasum(long long x) {
  long long ans = 0;
  while (x) {
    ans += x % 10;
    x /= 10;
  }
  return ans;
}
inline long long lcm(long long x, long long y) {
  long long ans = x / gcd(x, y) * y;
  return ans;
}
long long twobeki(long long x) {
  long long ans = 0;
  while (1) {
    if (!(x & 1)) {
      ans++;
      x >>= 1;
    } else {
      break;
    }
  }
  return ans;
}
template <class T, class U>
inline bool chmax(T &lhs, const U &rhs) {
  if (lhs < rhs) {
    lhs = rhs;
    return 1;
  }
  return 0;
}
template <class T, class U>
inline bool chmin(T &lhs, const U &rhs) {
  if (lhs > rhs) {
    lhs = rhs;
    return 1;
  }
  return 0;
}
void Yes() { cout << "Yes" << endl; }
void No() { cout << "No" << endl; }
void YES() { cout << "YES" << endl; }
void NO() { cout << "NO" << endl; }
long long kai(long long x, long long y) {
  long long res = 1;
  for (long long i = x - y + 1; i <= x; i++) {
    res *= i;
    res %= 1000000007ll;
  }
  return res;
}
long long comb(long long x, long long y) {
  if (y > x) return 0;
  return kai(x, y) * modpow(kai(y, y), 1000000007ll - 2) % 1000000007ll;
}
template <typename T>
class kaageSegTree {
 protected:
  unsigned long long n = 1, rank = 0;
  std::vector<T> node;
  T nodee;
  virtual T nodef(const T &, const T &) const = 0;

 public:
  kaageSegTree(unsigned long long m, T init, T nodee) : nodee(nodee) {
    while (n < m) {
      n *= 2;
      rank++;
    }
    node.resize(2 * n);
    for (unsigned long long i = n; i < 2 * n; i++) node[i] = init;
  }
  kaageSegTree(const std::vector<T> &initvec, T nodee) : nodee(nodee) {
    unsigned long long m = initvec.size();
    while (n < m) {
      n *= 2;
      rank++;
    }
    node.resize(2 * n);
    for (unsigned long long i = n; i < 2 * n; i++) {
      if (i - n < m) node[i] = initvec[i - n];
    }
  }
  virtual void update(long long i, T x) {
    i += n;
    node[i] = x;
    while (i != 1) {
      i >>= 1;
      node[i] = nodef(node[2 * i], node[2 * i + 1]);
    }
  }
  virtual T query(long long l, long long r) {
    l += n;
    r += n;
    T ls = nodee, rs = nodee;
    while (l < r) {
      if (l & 1) {
        ls = nodef(ls, node[l]);
        l++;
      }
      if (r & 1) {
        r--;
        rs = nodef(node[r], rs);
      }
      l >>= 1;
      r >>= 1;
    }
    return nodef(ls, rs);
  }
  virtual T operator[](const long long &x) { return node[n + x]; }
  void fill(T x) { std::fill(node.begin(), node.end(), x); }
  void print() {
    for (long long i = 0; i < n; i++) std::cout << operator[](i) << " ";
    std::cout << std::endl;
  }
};
class RSQ : public kaageSegTree<long long> {
  long long nodef(const long long &lhs, const long long &rhs) const {
    return lhs + rhs;
  }

 public:
  RSQ(long long size, const long long &def = 0)
      : kaageSegTree<long long>(size, def, 0) {}
  RSQ(const std::vector<long long> &initvec)
      : kaageSegTree<long long>(initvec, 0) {}
};
class RMiQ : public kaageSegTree<long long> {
  long long nodef(const long long &lhs, const long long &rhs) const {
    return std::min(lhs, rhs);
  }

 public:
  RMiQ(long long size, const long long &def = 0)
      : kaageSegTree<long long>(size, def, (long long)(3e18)) {}
  RMiQ(const std::vector<long long> &initvec)
      : kaageSegTree<long long>(initvec, (long long)(3e18)) {}
};
class RMaQ : public kaageSegTree<long long> {
  long long nodef(const long long &lhs, const long long &rhs) const {
    return std::max(lhs, rhs);
  }

 public:
  RMaQ(long long size, const long long &def = 0)
      : kaageSegTree<long long>(size, def, -(long long)(3e18)) {}
  RMaQ(const std::vector<long long> &initvec)
      : kaageSegTree<long long>(initvec, -(long long)(3e18)) {}
};
template <typename T, typename U>
class IntervalSegTree : public kaageSegTree<T> {
 protected:
  using kaageSegTree<T>::n;
  using kaageSegTree<T>::rank;
  using kaageSegTree<T>::node;
  using kaageSegTree<T>::nodef;
  using kaageSegTree<T>::nodee;
  std::vector<U> lazy;
  std::vector<bool> lazyflag;
  std::vector<long long> width;
  virtual void lazyf(U &, const U &) = 0;
  virtual void updf(T &, const U &, const unsigned long long &) = 0;
  void eval(long long k) {
    for (long long i = rank; i > 0; i--) {
      long long nk = k >> i;
      if (lazyflag[nk]) {
        updf(node[2 * nk], lazy[nk], width[2 * nk]);
        updf(node[2 * nk + 1], lazy[nk], width[2 * nk + 1]);
        if (lazyflag[2 * nk])
          lazyf(lazy[2 * nk], lazy[nk]);
        else
          lazy[2 * nk] = lazy[nk];
        if (lazyflag[2 * nk + 1])
          lazyf(lazy[2 * nk + 1], lazy[nk]);
        else
          lazy[2 * nk + 1] = lazy[nk];
        lazyflag[2 * nk] = lazyflag[2 * nk + 1] = true;
        lazyflag[nk] = false;
      }
    }
  }

 public:
  IntervalSegTree(unsigned long long m, T init, T nodee)
      : kaageSegTree<T>(m, init, nodee) {
    lazy.resize(2 * n);
    lazyflag.resize(2 * n);
    width.resize(2 * n);
    width[1] = n;
    for (unsigned long long i = 2; i < 2 * n; i++) {
      width[i] = width[i >> 1] >> 1;
    }
  }
  IntervalSegTree(T nodee, const std::vector<T> &initvec)
      : kaageSegTree<T>(initvec, nodee) {
    lazy.resize(2 * n);
    lazyflag.resize(2 * n);
    width.resize(2 * n);
    width[1] = n;
    for (unsigned long long i = 2; i < 2 * n; i++) {
      width[i] = width[i >> 1] >> 1;
    }
  }
  void update(long long i, U x) {
    i += n;
    eval(i);
    updf(node[i], x, width[i]);
    if (lazyflag[i])
      lazyf(lazy[i], x);
    else {
      lazyflag[i] = true;
      lazy[i] = x;
    }
    while (i /= 2) node[i] = nodef(node[2 * i], node[2 * i + 1]);
  }
  void update(long long l, long long r, U x) {
    l += n;
    r += n;
    long long nl = l, nr = r;
    while (!(nl & 1)) nl >>= 1;
    while (!(nr & 1)) nr >>= 1;
    nr--;
    eval(nl);
    eval(nr);
    while (l < r) {
      if (l & 1) {
        updf(node[l], x, width[l]);
        if (lazyflag[l])
          lazyf(lazy[l], x);
        else {
          lazyflag[l] = true;
          lazy[l] = x;
        }
        l++;
      }
      if (r & 1) {
        r--;
        updf(node[r], x, width[r]);
        if (lazyflag[r])
          lazyf(lazy[r], x);
        else {
          lazyflag[r] = true;
          lazy[r] = x;
        }
      }
      l >>= 1;
      r >>= 1;
    }
    while (nl >>= 1) node[nl] = nodef(node[2 * nl], node[2 * nl + 1]);
    while (nr >>= 1) node[nr] = nodef(node[2 * nr], node[2 * nr + 1]);
  }
  T query(long long l, long long r) {
    l += n;
    r += n;
    eval(l);
    eval(r - 1);
    long long ls = nodee, rs = nodee;
    while (l < r) {
      if (l & 1) {
        ls = nodef(ls, node[l]);
        l++;
      }
      if (r & 1) {
        r--;
        rs = nodef(node[r], rs);
      }
      l >>= 1;
      r >>= 1;
    }
    return nodef(ls, rs);
  }
  T operator[](const long long &x) {
    eval(n + x);
    return node[n + x];
  }
  T queryForAll() { return node[1]; }
};
class RAQRSQ : public IntervalSegTree<long long, long long> {
  long long nodef(const long long &a, const long long &b) const {
    return a + b;
  }
  void lazyf(long long &a, const long long &b) { a += b; }
  void updf(long long &a, const long long &b, const unsigned long long &width) {
    a += width * b;
  }

 public:
  RAQRSQ(long long size, const long long &def = 0)
      : IntervalSegTree<long long, long long>(size, def, 0) {
    for (long long i = n - 1; i > 0; i--)
      node[i] = nodef(node[2 * i], node[2 * i + 1]);
  }
  RAQRSQ(const std::vector<long long> &initvec)
      : IntervalSegTree<long long, long long>((long long)0, initvec) {
    for (long long i = n - 1; i > 0; i--)
      node[i] = nodef(node[2 * i], node[2 * i + 1]);
  }
};
class RAQRMiQ : public IntervalSegTree<long long, long long> {
  long long nodef(const long long &a, const long long &b) const {
    return std::min(a, b);
  }
  void lazyf(long long &a, const long long &b) { a += b; }
  void updf(long long &a, const long long &b, const unsigned long long &width) {
    a += b;
  }

 public:
  RAQRMiQ(long long size, const long long &def = 0)
      : IntervalSegTree<long long, long long>(size, def, (long long)(3e18)) {
    for (long long i = n - 1; i > 0; i--)
      node[i] = nodef(node[2 * i], node[2 * i + 1]);
  }
  RAQRMiQ(const std::vector<long long> &initvec)
      : IntervalSegTree<long long, long long>((long long)(3e18), initvec) {
    for (long long i = n - 1; i > 0; i--)
      node[i] = nodef(node[2 * i], node[2 * i + 1]);
  }
};
class RAQRMaQ : public IntervalSegTree<long long, long long> {
  long long nodef(const long long &a, const long long &b) const {
    return std::max(a, b);
  }
  void lazyf(long long &a, const long long &b) { a += b; }
  void updf(long long &a, const long long &b, const unsigned long long &width) {
    a += b;
  }

 public:
  RAQRMaQ(unsigned long long size, const long long &def = 0)
      : IntervalSegTree<long long, long long>(size, def, -(long long)(3e18)) {
    for (long long i = n - 1; i > 0; i--)
      node[i] = nodef(node[2 * i], node[2 * i + 1]);
  }
  RAQRMaQ(const std::vector<long long> &initvec)
      : IntervalSegTree<long long, long long>(-(long long)(3e18), initvec) {
    for (long long i = n - 1; i > 0; i--)
      node[i] = nodef(node[2 * i], node[2 * i + 1]);
  }
};
class RUQRSQ : public IntervalSegTree<long long, long long> {
  long long nodef(const long long &a, const long long &b) const {
    return a + b;
  }
  void lazyf(long long &a, const long long &b) { a = b; }
  void updf(long long &a, const long long &b, const unsigned long long &width) {
    a = width * b;
  }

 public:
  RUQRSQ(long long size, const long long &def = 0)
      : IntervalSegTree<long long, long long>(size, def, 0) {
    for (long long i = n - 1; i > 0; i--)
      node[i] = nodef(node[2 * i], node[2 * i + 1]);
  }
  RUQRSQ(const std::vector<long long> &initvec)
      : IntervalSegTree<long long, long long>((long long)0, initvec) {
    for (long long i = n - 1; i > 0; i--)
      node[i] = nodef(node[2 * i], node[2 * i + 1]);
  }
};
class RUQRMiQ : public IntervalSegTree<long long, long long> {
  long long nodef(const long long &a, const long long &b) const {
    return std::min(a, b);
  }
  void lazyf(long long &a, const long long &b) { a = b; }
  void updf(long long &a, const long long &b, const unsigned long long &width) {
    a = b;
  }

 public:
  RUQRMiQ(long long size, const long long &def = 0)
      : IntervalSegTree<long long, long long>(size, def, (long long)(3e18)) {
    for (long long i = n - 1; i > 0; i--)
      node[i] = nodef(node[2 * i], node[2 * i + 1]);
  }
  RUQRMiQ(const std::vector<long long> &initvec)
      : IntervalSegTree<long long, long long>((long long)(3e18), initvec) {
    for (long long i = n - 1; i > 0; i--)
      node[i] = nodef(node[2 * i], node[2 * i + 1]);
  }
};
class RUQRMaQ : public IntervalSegTree<long long, long long> {
  long long nodef(const long long &a, const long long &b) const {
    return std::max(a, b);
  }
  void lazyf(long long &a, const long long &b) { a = b; }
  void updf(long long &a, const long long &b, const unsigned long long &width) {
    a = b;
  }

 public:
  RUQRMaQ(long long size, const long long &def = 0)
      : IntervalSegTree<long long, long long>(size, def, -(long long)(3e18)) {
    for (long long i = n - 1; i > 0; i--)
      node[i] = nodef(node[2 * i], node[2 * i + 1]);
  }
  RUQRMaQ(const std::vector<long long> &initvec)
      : IntervalSegTree<long long, long long>(-(long long)(3e18), initvec) {
    for (long long i = n - 1; i > 0; i--)
      node[i] = nodef(node[2 * i], node[2 * i + 1]);
  }
};
template <class T>
class SegTree {
  long long n;
  vector<T> node;
  T def;
  function<T(T, T)> operation;
  function<T(T, T)> update;

 public:
  SegTree(unsigned long long _n, T _def, function<T(T, T)> _operation,
          function<T(T, T)> _update)
      : def(_def), operation(_operation), update(_update) {
    n = 1;
    while (n < _n) {
      n *= 2;
    }
    node = vector<T>(n * 2, def);
  }
  SegTree(vector<long long> &initvec, function<T(T, T)> _operation,
          function<T(T, T)> _update)
      : operation(_operation), update(_update) {
    n = 1;
    while (n < initvec.size()) {
      n *= 2;
    }
    node = vector<T>(n * 2, def);
    for (long long i = n; i < n + initvec.size(); i++) {
      node[i] = initvec[i - n];
    }
    for (long long i = n - 1; i >= 1; i--) {
      node[i] = operation(node[i * 2], node[i * 2 + 1]);
    }
  }
  void change(long long i, T x) {
    i += n;
    node[i] = update(node[i], x);
    while (i >= 1) {
      i >>= 1;
      node[i] = operation(node[i * 2], node[i * 2 + 1]);
    }
  }
  T query(long long l, long long r) {
    l += n;
    r += n;
    T rx = def, lx = def;
    while (l < r) {
      if (l & 1) {
        lx = operation(lx, node[l]);
        l++;
      }
      if (r & 1) {
        r--;
        rx = operation(node[r], rx);
      }
      l >>= 1;
      r >>= 1;
    }
    return operation(lx, rx);
  }
  T operator[](const long long &x) { return node[x + n]; }
  void fill(T x) { std::fill(node.begin(), node.end(), x); }
  void print() {
    for (long long i = 0; i < n; i++) std::cout << operator[](i) << " ";
    std::cout << std::endl;
  }
};
class Union_Find {
  vector<long long> par;
  vector<long long> rankmy;
  vector<long long> ookisa;

 public:
  Union_Find(long long size) {
    par = vector<long long>(size);
    rankmy = vector<long long>(size);
    ookisa = vector<long long>(size);
    for (long long i = 0; i < size; i++) {
      par[i] = i;
      ookisa[i] = 1;
    }
  }
  long long find(long long x) {
    if (par[x] == x) {
      return x;
    }
    return par[x] = find(par[x]);
  }
  void unite(long long x, long long y) {
    x = find(x);
    y = find(y);
    if (x == y) {
      return;
    }
    if (rankmy[x] < rankmy[y]) {
      par[x] = y;
      ookisa[y] += ookisa[x];
      ookisa[x] = 0;
    } else {
      par[y] = x;
      ookisa[x] += ookisa[y];
      ookisa[y] = 0;
      if (rankmy[x] == rankmy[y]) {
        rankmy[x]++;
      }
    }
  }
  long long size(long long i) {
    i = find(i);
    return ookisa[i];
  }
  bool same(long long x, long long y) { return find(x) == find(y); }
};
class BIT {
  vector<long long> data;
  long long size = 0;

 public:
  BIT(long long _size) {
    data = vector<long long>(_size + 1);
    size = _size;
  }
  void add(long long i, long long x) {
    while (i <= size) {
      data[i] += x;
      i += i & -i;
    }
  }
  long long sum(long long i) {
    assert(i <= size);
    long long s = 0;
    while (i > 0) {
      s += data[i];
      i -= i & -i;
    }
    return s;
  }
  long long lower_bound(long long x) {
    if (x <= 0) {
      return 0;
    } else {
      long long i = 0;
      long long r = 1;
      while (r < size) r = r << 1;
      for (long long len = r; len > 0; len = len >> 1) {
        if (i + len < size && data[i + len] < x) {
          x -= data[i + len];
          i += len;
        }
      }
      return i + 1;
    }
  }
};
long long perm[2000005];
void init_perm() {
  perm[0] = 1;
  for (long long i = 1; i <= 2000004; i++) {
    perm[i] = perm[i - 1] * i % 1000000007ll;
  }
}
long long nCk(long long x, long long y) {
  if (y > x) {
    return 0;
  }
  if (x < 0) {
    return 0;
  }
  return perm[x] * modpow(perm[x - y], 1000000007ll - 2) % 1000000007ll *
         modpow(perm[y], 1000000007ll - 2) % 1000000007ll;
}
double kyori(pair<long long, long long> f, pair<long long, long long> s) {
  double ans = 0;
  double t = fabs(f.first - s.first);
  double y = fabs(f.second - s.second);
  ans = sqrt(t * t + y * y);
  return ans;
}
inline string stringmax(string &x, string &y) {
  if (x.size() > y.size()) {
    return x;
  }
  if (x.size() < y.size()) {
    return y;
  }
  for (long long i = 0; i < x.size(); i++) {
    if (x[i] > y[i]) {
      return x;
    }
    if (x[i] < y[i]) {
      return y;
    }
  }
  return x;
}
struct edge {
  long long to;
  long long length;
  edge(long long _to, long long _length) {
    to = _to;
    length = _length;
  }
};
vector<long long> djkstra(vector<vector<edge>> &road, long long start) {
  vector<long long> kyo(road.size(), (long long)(3e18));
  priority_queue<pair<long long, long long>, vector<pair<long long, long long>>,
                 greater<pair<long long, long long>>>
      q;
  q.push({0, start});
  kyo[start] = 0;
  while (q.size()) {
    long long x = q.top().second;
    long long now = q.top().first;
    q.pop();
    if (kyo[x] < now) {
      continue;
    }
    for (auto &i : road[x]) {
      if (kyo[i.to] > now + i.length) {
        kyo[i.to] = now + i.length;
        q.push({kyo[i.to], i.to});
      }
    }
  }
  return kyo;
}
template <class T>
void change_to_unique(vector<T> &v) {
  std::sort(v.begin(), v.end());
  auto k = unique(v.begin(), v.end());
  if (k != v.end()) v.erase(k, v.end());
}
long long t, gou;
long long dfs(vector<long long> &chi, vector<vector<edge>> &road, long long x,
              long long par) {
  long long cnt = 1;
  if (road[x].size() > 1) {
    cnt--;
  }
  for (auto &i : road[x]) {
    if (i.to == par) {
      continue;
    }
    cnt += dfs(chi, road, i.to, x);
  }
  return chi[x] = cnt;
}
void dfs2(vector<long long> &chi,
          priority_queue<pair<pair<long long, long long>, long long>> &q,
          vector<vector<edge>> &road, long long x, long long par,
          long long kyo) {
  gou += kyo;
  if (road[x].size() > 1) {
    gou -= kyo;
  }
  for (auto &i : road[x]) {
    if (i.to == par) {
      continue;
    }
    dfs2(chi, q, road, i.to, x, kyo + i.length);
    q.push({{(i.length - i.length / 2) * chi[i.to], i.to}, i.length});
  }
}
signed main() {
  ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  cin >> t;
  for (long long _ = 0; _ < t; _++) {
    long long n, s;
    gou = 0;
    cin >> n >> s;
    vector<long long> v(n + 1), u(n + 1), c(n + 1);
    vector<vector<edge>> road(n + 1);
    vector<long long> chi(n + 1);
    for (long long i = 0; i < n - 1; i++) {
      cin >> v[i] >> u[i] >> c[i];
      road[v[i]].emplace_back(edge(u[i], c[i]));
      road[u[i]].emplace_back(edge(v[i], c[i]));
    }
    dfs(chi, road, 1, 0);
    priority_queue<pair<pair<long long, long long>, long long>> q;
    dfs2(chi, q, road, 1, 0, 0);
    long long cnt = 0;
    while (gou > s) {
      cnt++;
      pair<pair<long long, long long>, long long> x = q.top();
      q.pop();
      gou -= x.first.first;
      x.second /= 2;
      if (x.second == 0) {
        cout << "\n";
      }
      q.push({{(x.second - x.second / 2) * chi[x.first.second], x.first.second},
              x.second});
    }
    cout << cnt << "\n";
  }
}