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 JAVA):

Solution:
/*
    Author: Anthony Ngene
    Created: 10/08/2020 - 12:20
*/

import java.io.*;
import java.util.*;

public class E2 {
    // Education is like a double-edged sword. It may be turned to dangerous uses if it is not properly handled. - Wu Ting-Fang
    static HashMap<Integer, HashMap<Integer, Tuple>> adj;
    public static void main(String[] args) throws IOException {
        in = new FastScanner();

        int cases = in.intNext();
        for (int t = 1; t <= cases; t++) {
            int n = in.intNext();
            long maxPathSums = in.longNext();
            adj = new HashMap<>();
            List<Tuple> edgesArr1 = new ArrayList<>();
            List<Tuple> edgesArr2 = new ArrayList<>();
            for (int i = 0; i < n - 1; i++) {
                int a = in.intNext(), b = in.intNext();
                long w = in.longNext();
                int cost = in.intNext();
                Tuple edge = new Tuple(w, i);
                if (!adj.containsKey(a)) adj.put(a, new HashMap<>());
                if (!adj.containsKey(b)) adj.put(b, new HashMap<>());
                adj.get(a).put(b, edge);
                adj.get(b).put(a, edge);
                if (cost == 1) edgesArr1.add(edge);
                else edgesArr2.add(edge);
            }
            dfs(1, new boolean[n + 1]);

            TreeSet<Tuple> edges1 = new TreeSet<>();
            TreeSet<Tuple> edges2 = new TreeSet<>();
            long total1 = 0;
            for (Tuple edge : edgesArr1) {
                total1 += edge.actualWeight();
                edges1.add(edge);
            }
            long total2 = 0;
            for (Tuple edge : edgesArr2) {
                total2 += edge.actualWeight();
                edges2.add(edge);
            }
            int moves = 0;
            if (edgesArr1.isEmpty()) moves = getMoves(maxPathSums, total2, edges2, 2);
            else if (edgesArr2.isEmpty()) moves = getMoves(maxPathSums, total1, edges1, 1);
            else moves = getMoves(maxPathSums, total1 + total2, edges1, edges2);

            out.println(moves);
        }

        out.close();
    }

    static int getMoves(long maxPathSums, long total, TreeSet<Tuple> edges, int incr) {
        int moves = 0;
        while (total > maxPathSums) {
            moves += incr;
            Tuple edge = edges.pollLast();
            total -= edge.select();
            edges.add(edge);
        }
        return moves;
    }

    static int getMoves(long maxPathSums, long total, TreeSet<Tuple> edges1, TreeSet<Tuple> edges2) {
        int moves = 0;
        while (total > maxPathSums) {
            if (total - edges1.last().savings() <= maxPathSums) return moves + 1;
            Tuple edge1 = edges1.pollLast();
            long save1 = edge1.savings();
            long save1_second = edge1.secondSavings();
            if (!edges1.isEmpty() && edges1.last().savings() > save1_second)
                save1_second = edges1.last().savings();
            save1 += save1_second;

            if (save1 > edges2.last().savings()) {
                total -= edge1.select();
                moves++;
            } else {
                Tuple edge2 = edges2.pollLast();
                total -= edge2.select();
                edges2.add(edge2);
                moves += 2;
            }
            edges1.add(edge1);
        }
        return moves;
    }

    static int dfs(int node, boolean[] visited) {
        visited[node] = true;
        int leaves = 0;
        for (int child : adj.get(node).keySet()) {
            if (!visited[child]) {
                int childLeaves = dfs(child, visited);
                leaves += childLeaves;
                adj.get(node).get(child).leaves = childLeaves;
            }
        }
        return max(leaves, 1);
    }

    static class Tuple implements Comparable<Tuple> {
        long weight;
        long id;
        long leaves = 1;
        public Tuple(long weight, long idx) {
            this.weight = weight;
            this.id = idx;
        }

        public long actualWeight() {
            return weight * leaves;
        }
        public long savings() {
            return (weight * leaves) - ((weight / 2) * leaves);
        }
        public long secondSavings() {
            return ((weight / 2) * leaves) - ((weight / 4) * leaves);
        }
        public long select() {
            long saving = savings();
            weight /= 2;
            return saving;
        }
        public int compareTo(Tuple other) {
            if (this.savings() == other.savings()) {
                return Long.compare(this.id, other.id);
            }
            return Long.compare(this.savings(), other.savings());
        }
        @Override
        public int hashCode() { return Arrays.deepHashCode(new Long[]{this.weight, this.leaves, this.id}); }
        @Override
        public String toString() { return String.format("(%d %d %d)  ", this.weight, this.leaves, this.id); }
    }
    // Generated Code Below:
    private static final FastWriter out = new FastWriter();
    private static FastScanner in;

    private static long e97 = (long)1e9 + 7;
    static class FastWriter {
        private static final int IO_BUFFERS = 128 * 1024;
        private final StringBuilder out;
        public FastWriter() { out = new StringBuilder(IO_BUFFERS); }
        public FastWriter p(Object object) { out.append(object); return this; }
        public FastWriter p(String format, Object... args) { out.append(String.format(format, args)); return this; }
        public FastWriter pp(Object... args) { for (Object ob : args) { out.append(ob).append(" ");  } out.append("\n"); return this; }
        public void println(long[] arr) { out.append(Arrays.toString(arr)).append("\n"); }
        public void println(int[] arr) { out.append(Arrays.toString(arr)).append("\n"); }
        public void println(char[] arr) { out.append(Arrays.toString(arr)).append("\n"); }
        public void println(float[] arr) { out.append(Arrays.toString(arr)).append("\n"); }
        public void println(boolean[] arr) { out.append(Arrays.toString(arr)).append("\n"); }
        public <T>void println(T[] arr) { out.append(Arrays.toString(arr)).append("\n"); }
        public void println(long[][] arr) {  for (long[] row: arr) out.append(Arrays.toString(row)).append(" "); out.append("\n");  }
        public void println(int[][] arr) {  for (int[] row: arr) out.append(Arrays.toString(row)).append(" "); out.append("\n");  }
        public void println(char[][] arr) {  for (char[] row: arr) out.append(Arrays.toString(row)).append(" "); out.append("\n");  }
        public void println(float[][] arr) {  for (float[] row: arr) out.append(Arrays.toString(row)).append(" "); out.append("\n");  }
        public <T>void println(T[][] arr) {  for (T[] row: arr) out.append(Arrays.toString(row)).append(" "); out.append("\n");  }
        public FastWriter println(Object object) { out.append(object).append("\n"); return this; }
        public void toFile(String fileName) throws IOException {
            BufferedWriter writer = new BufferedWriter(new FileWriter(fileName));
            writer.write(out.toString());
            writer.close();
        }
        public void close() throws IOException { System.out.print(out); }
    }
    static class FastScanner {
        private InputStream sin = System.in;
        private final byte[] buffer = new byte[1024];
        private int ptr = 0;
        private int buflen = 0;
        public FastScanner(){}
        public FastScanner(String filename) throws FileNotFoundException {
            File file = new File(filename);
            sin = new FileInputStream(file);
        }
        private boolean hasNextByte() {
            if (ptr < buflen) {
                return true;
            }else{
                ptr = 0;
                try {
                    buflen = sin.read(buffer);
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (buflen <= 0) {
                    return false;
                }
            }
            return true;
        }
        private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1;}
        private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
        public boolean hasNext() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; return hasNextByte();}
        public String next() {
            if (!hasNext()) throw new NoSuchElementException();
            StringBuilder sb = new StringBuilder();
            int b = readByte();
            while(isPrintableChar(b)) {
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }
        public long longNext() {
            if (!hasNext()) throw new NoSuchElementException();
            long n = 0;
            boolean minus = false;
            int b = readByte();
            if (b == '-') {
                minus = true;
                b = readByte();
            }
            if (b < '0' || '9' < b) {
                throw new NumberFormatException();
            }
            while(true){
                if ('0' <= b && b <= '9') {
                    n *= 10;
                    n += b - '0';
                }else if(b == -1 || !isPrintableChar(b) || b == ':'){
                    return minus ? -n : n;
                }else{
                    throw new NumberFormatException();
                }
                b = readByte();
            }
        }
        public int intNext() {
            long nl = longNext();
            if (nl < Integer.MIN_VALUE || nl > Integer.MAX_VALUE) throw new NumberFormatException();
            return (int) nl;
        }
        public double doubleNext() { return Double.parseDouble(next());}
        public long[] nextLongArray(final int n){
            final long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = longNext();
            return a;
        }
        public int[] nextIntArray(final int n){
            final int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = intNext();
            return a;
        }
        public ArrayList<Integer>[] getAdj(int n) {
            ArrayList<Integer>[] adj = new ArrayList[n + 1];
            for (int i = 1; i <= n; i++) adj[i] = new ArrayList<>();
            return adj;
        }
    }

    private static int max(int... ins){ int max = ins[0]; for(int i=1; i<ins.length; i++){ if(ins[i] > max) max = ins[i]; } return max; }
}