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: 06/08/2020 - 16:51
*/

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

public class E2 {
    // You must be the change you wish to see in the world. - Mahatma Gandhi
    static HashMap<Long, HashMap<Long, Tuple3>> adj;
    static int uniqueId;
    static ArrayList<Tuple3> oneVerticesList;
    static ArrayList<Tuple3> twoVerticesList;
    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 s = in.longNext();
            adj = new HashMap<>();
            uniqueId = 0;
            oneVerticesList = new ArrayList<>();
            twoVerticesList = new ArrayList<>();
            for (int i = 0; i < n - 1; i++) {
                long a = in.longNext();
                long b = in.longNext();
                long w = in.longNext();
                int cost = in.intNext();
                addVertex(a, b, w, cost, adj);
            }

            visited = new boolean[n + 1];
            dfs(1);
            TreeSet<Tuple3> oneVertices = new TreeSet<>();
            TreeSet<Tuple3> twoVertices = new TreeSet<>();
            long total = 0;
            for (Tuple3 vertex : oneVerticesList) {
                total += vertex.a;
                oneVertices.add(vertex);
            }
            for (Tuple3 vertex : twoVerticesList) {
                total += vertex.a;
                twoVertices.add(vertex);
            }
            int ans = 0;
//            out.println(twoVertices);
//            out.println(oneVertices);
            while (total > s) {
                if (oneVertices.size() > 0 && total - oneVertices.last().savings() <= s) {
//                    out.println("hi");
                    ans++;
                    break;
                }
                if (oneVertices.size() == 0) {
                    Tuple3 v = twoVertices.pollLast();
                    total -= v.choose();
                    twoVertices.add(v);
                    ans += 2;
                } else if (twoVertices.size() == 0) {
                    Tuple3 v = oneVertices.pollLast();
                    total -= v.choose();
                    oneVertices.add(v);
                    ans++;
                } else {
                    Tuple3 v1 = oneVertices.pollLast();
                    long savings1 = v1.savings();
                    long newB = v1.b / 2;
                    long savings12 = (newB - newB/2) * v1.count;
                    if (oneVertices.size() > 0 && oneVertices.last().savings() > savings12)
                        savings12 = oneVertices.last().savings();
                    if (twoVertices.last().savings() > savings1 + savings12) {
                        Tuple3 v = twoVertices.pollLast();
                        total -= v.choose();
                        twoVertices.add(v);
                        ans += 2;
                    } else {
                        total -= v1.choose();
                        oneVertices.add(v1);
                        ans++;
                    }
                    oneVertices.add(v1);

                }
//                out.println(twoVertices);
//                out.println(oneVertices);
            }

//            out.println(vertices);
            out.println(ans);
        }

        out.close();
    }

    static boolean[] visited;
    static int dfs(long node) {
        visited[(int)node] = true;
        int leaves = 0;
        for (long child: adj.get(node).keySet()) {
            if (!visited[(int) child]) {
                int childLeaves = dfs(child);
                Tuple3 vertex = adj.get(node).get(child);
                vertex.count = childLeaves;
                vertex.a = vertex.b * vertex.count;
                leaves += childLeaves;
            }
        }
        return leaves == 0 ? 1 : leaves;
    }

    static void addVertex(long a, long b, long w, int cost, HashMap<Long, HashMap<Long, Tuple3>> adj) {
        if (!adj.containsKey(a)) adj.put(a, new HashMap<>());
        if (!adj.containsKey(b)) adj.put(b, new HashMap<>());
        Tuple3 vertex = new Tuple3(0, w, uniqueId, cost);
        uniqueId++;
        adj.get(a).put(b, vertex);
        adj.get(b).put(a, vertex);
        if (cost == 1) oneVerticesList.add(vertex);
        else twoVerticesList.add(vertex);
    }

    static class Tuple3 implements Comparable<Tuple3> {
        long a;
        long b;
        long c;
        long count;
        int cost;

        public Tuple3(long a, long b, long id, int cost) {
            this.a = a;
            this.b = b;
            this.c = id;
            this.count = 0;
            this.cost = cost;
        }

        public long savings() {
            return a - (b / 2) * count;
        }
        public long choose() {
            long save = savings();
            b /= 2;
            a = b * count;
            return save;
        }

        public long getA() {
            return a;
        }

        public long getB() {
            return b;
        }

        public long getC() {
            return c;
        }

        public int compareTo(Tuple3 other) {
            long sa = ((this.b - this.b/2) * this.count);
            long sb = ((other.b - other.b / 2) * other.count);
            if (sa == sb) {
                return Long.compare(this.c, other.c);
            }
            return sa > sb ? 1 : -1;
        }

        @Override
        public int hashCode() {
            return Arrays.deepHashCode(new Long[]{a, b, c});
        }

        @Override
        public boolean equals(Object o) {
            if (!(o instanceof Tuple3)) return false;
            Tuple3 pairo = (Tuple3) o;
            return (this.a == pairo.a && this.b == pairo.b && this.c == pairo.c);
        }

        @Override
        public String toString() {
            return String.format("(%d %d %d)  ", this.a, this.b, this.c);
        }
    }

    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 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;
        }
    }
}