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:
import java.io.DataInputStream; 
import java.io.FileInputStream; 
import java.io.IOException; 
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.io.BufferedReader; 
import java.util.*;
import java.math.BigInteger; 


public class E2{
	public static FastReader fs = new FastReader();
	static ArrayList<edge> adj [];
	static long leaves [],sum = 0;
	static long req_benifit;
	static PriorityQueue<comp> one,two;
	static ArrayList<Long> one_benifit,two_benifit;
	static int token = 0;
	static PrintWriter out = new PrintWriter(System.out);
	
	static boolean is_leave(int node) {
		return adj[node].size() == 1 && node != 0;
	}
	
	static class comp implements Comparable<comp> {
		long weight,nleaves;
		comp(long we,long nl){
			this.weight = we;
			this.nleaves = nl;
		}
		public int compareTo(comp o) {
			return -Long.compare((this.weight - (this.weight / 2))*this.nleaves, (o.weight - (o.weight / 2))*o.nleaves);
		}
	}
	
	static class edge{
		int to;
		long we;
		long charge;
		edge(int e,long c,long ch){
			this.to = e;
			this.we = c;
			this.charge = ch;
		}
	}
	
	static void dfs(int node,int pr) {
		if(is_leave(node)) {
			leaves[node] = 1l;
			return;
		}
		for(edge to : adj[node]) {
			if(to.to == pr)continue;
			dfs(to.to,node);
			sum += (to.we*leaves[to.to]);
			if(to.charge == 1)
			one.add(new comp(to.we,leaves[to.to]));
			else {
				two.add(new comp(to.we,leaves[to.to]));
			}
			leaves[node] += leaves[to.to];
		}
	}
	
	static int in_two(long val,ArrayList<Long> x) {
		int start = 0,end = x.size()-1;
		int ans = -1;
		while(start <= end) {
			int mid = start + (end - start) / 2;
			if(x.get(mid) >= val) {
				ans = mid;
				end = mid-1;
			}
			else start = mid+1;
		}
		return ans;
	}
	
	static void solve() {
		StringBuffer output = new StringBuffer();
		one_benifit = new ArrayList<>();two_benifit = new ArrayList<>();
		sum = 0;token = 0;
		int n = fs.nextInt();long req_sum = fs.nextLong();
		adj = new ArrayList[n];
		leaves = new long [n];
		for(int i = 0; i<n; i++) {
			adj[i] = new ArrayList<edge>();
		}
		for(int i = 0; i<n-1; i++) {
			int x = fs.nextInt()-1,y = fs.nextInt()-1;long we = fs.nextLong(),ch = fs.nextLong();
			adj[x].add(new edge(y,we,ch));
			adj[y].add(new edge(x,we,ch));
		}
		one = new PriorityQueue<comp> ();two = new PriorityQueue<>();
		dfs(0,-1);
		req_benifit = sum - req_sum;
		if(req_benifit <= 0) {
			out.println(0);
			return;
		}
		long ans = Long.MAX_VALUE;
		while(!one.isEmpty()) {
			comp c = one.poll();
			if(one_benifit.isEmpty())
				one_benifit.add((c.weight - (c.weight / 2))*c.nleaves);
				else {
					one_benifit.add(one_benifit.get(one_benifit.size()-1) + (c.weight - (c.weight / 2))*c.nleaves);
				}
			c.weight /= 2;
			if(c.weight > 0)one.add(c);
		}
		while(!two.isEmpty()) {
			comp c = two.poll();
			if(two_benifit.isEmpty())
			two_benifit.add((c.weight - (c.weight / 2))*c.nleaves);
			else {
				two_benifit.add(two_benifit.get(two_benifit.size()-1) + (c.weight - (c.weight / 2))*c.nleaves);
			}
			c.weight /= 2;
			if(c.weight > 0)two.add(c);
		}
		int y = two_benifit.size()-1;
		for(int x = 0; x < one_benifit.size(); x++){
			if(one_benifit.get(x) >= req_benifit)
				ans = min(ans,x+1);
			while(y > 0 && one_benifit.get(x) + two_benifit.get(y-1) >= req_benifit){
				y--;
			}
			if(y >= 0 && one_benifit.get(x) + two_benifit.get(y) >= req_benifit)
				ans = min(ans,(x+1) + 2*(y+1));
		}
		
		for(y = 0; y<two_benifit.size(); y++){
			if(two_benifit.get(y) >= req_benifit)
				ans = min(ans, 2*(y+1));
		}
		out.println(ans);
	}
	
	public static void main(String[] args) {
		Thread t = new Thread(null,null,"",1 << 28) {
			public void run() {
				int test_case = 1;
				test_case = fs.nextInt();
				for(int cs = 1; cs <= test_case; cs++) {
					solve();
				}
				out.close();
			}
		};
		t.start();
		try {
			t.join();
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
	}
	static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
        int [] readintarray(int n) {
        	int res [] = new int [n];
        	for(int i = 0; i<n; i++)res[i] = nextInt();
        	return res;
        }
        long [] readlongarray(int n) {
        	long res [] = new long [n];
        	for(int i = 0; i<n; i++)res[i] = nextLong();
        	return res;
        }
    } 
	
	static int ceil(int x,int y) {
		return (x % y == 0 ? x / y : (x / y +1));
	}
	
	static long ceil(long x,long y) {
		return (x % y == 0 ? x / y : (x / y +1));
	}
	
	static int max(int x,int y) {
		return Math.max(x, y);
	}
	
	static int min(int x,int y) {
		return Math.min(x, y);
	}
	
	static long max(long x,long y) {
		return Math.max(x, y);
	}
	
	static long min(long x,long y) {
		return Math.min(x, y);
	}
	
	static int min(int a []) {
		int x = 1_000_000_00_9;
		for(int i = 0; i<a.length; i++)x = min(x,a[i]);
		return x;
	}
	
	static int max(int a []) {
		int x = -1_000_000_00_9;
		for(int i = 0; i<a.length; i++)x = max(x,a[i]);
		return x;
	}
	
	static long min(long a []) {
		long x = (long)3e18;
		for(int i = 0; i<a.length; i++)x = min(x,a[i]);
		return x;
	}
	
	static long max(long a []) {
		long x = -(long)3e18;
		for(int i = 0; i<a.length; i++)x = max(x,a[i]);
		return x;
	}
	
	static int power(int x,int y) {
		int res = 1;
		while(y > 0) {
			if( y % 2 == 1)res = (res * x);
			y >>= 1;
            x = (x * x);
		}
		return res;
	}
	
	static long power(long x,long y) {
		long res = 1;
		while(y > 0) {
			if( y % 2 == 1)res = (res * x);
			y >>= 1;
            x = (x * x);
		}
		return res;
	}
	
	static long power(long x,long y,long mod) {
		long res = 1;
		x %= mod;
		while(y > 0) {
			if( y % 2 == 1)res = (res * x) % mod;
			y >>= 1;
            x = (x * x) % mod;
		}
		return res;
	}
	
	static void intsort(int [] a) {
		List<Integer> temp = new ArrayList<Integer>();
		for(int i = 0; i<a.length; i++)temp.add(a[i]);
		Collections.sort(temp);
		for(int i = 0; i<a.length; i++)a[i] = temp.get(i);
	}
	
	static void longsort(long [] a) {
		List<Long> temp = new ArrayList<Long>();
		for(int i = 0; i<a.length; i++)temp.add(a[i]);
		Collections.sort(temp);
		for(int i = 0; i<a.length; i++)a[i] = temp.get(i);
	}
	
	static void reverseintsort(int [] a) {
		List<Integer> temp = new ArrayList<Integer>();
		for(int i = 0; i<a.length; i++)temp.add(a[i]);
		Collections.sort(temp);
		Collections.reverseOrder();
		for(int i = 0; i<a.length; i++)a[i] = temp.get(i);
	}
	
	static void reverselongsort(long [] a) {
		List<Long> temp = new ArrayList<Long>();
		for(int i = 0; i<a.length; i++)temp.add(a[i]);
		Collections.sort(temp);
		Collections.reverseOrder();
		for(int i = 0; i<a.length; i++)a[i] = temp.get(i);
	}
	
	static void intpairsort(intpair [] a) {
		List<intpair> temp = new ArrayList<intpair>();
		for(int i = 0; i<a.length; i++)temp.add(a[i]);
		Collections.sort(temp,(p1,p2) -> {
			if(p1.x == p2.x) return p1.y >= p2.y ? -1 : 1;
			else return p1.x > p2.x ? -1 : 1;
		});
		for(int i = 0; i<a.length; i++)a[i] = temp.get(i);
	}
	
	static void longpairsort(longpair [] a) {
		List<longpair> temp = new ArrayList<longpair>();
		for(int i = 0; i<a.length; i++)temp.add(a[i]);
		Collections.sort(temp,(p1,p2) -> {
			if(p1.x == p2.x) return p1.y >= p2.y ? -1 : 1;
			else return p1.x > p2.x ? -1 : 1;
		});
		for(int i = 0; i<a.length; i++)a[i] = temp.get(i);
	}
	
	static class intpair{
		public int x;
		public int y;
		
		intpair(int a,int b){
			this.x = a;
			this.y = b;
		}
		
		intpair(){}
	}
	
	static class longpair{
		public long x;
		public long y;
		
		longpair(long a,long b){
			this.x = a;
			this.y = b;
		}
		
		longpair(){}
	}
	
	static class data{
		public long sum;
		
		data(long val){
		    this.sum = val;
		}
		
		data(){}
		
		data combine(data l, data r) {
		    data res = new data();
		    res.sum = l.sum + r.sum;
		    return res;
		}
	}
	
	static class Seg_Tree extends data{
		public int n;
		data [] seg;
		
		Seg_Tree(int sz){
			this.n = sz;
			seg = new data[4*n+4];
		}
		
		void build(long a[], int v, int tl, int tr) {
		    if (tl == tr) {
		        seg[v] = new data(a[tl]);
		    } else {
		        int tm = (tl + tr) / 2;
		        build(a, v*2, tl, tm);
		        build(a, v*2+1, tm+1, tr);
		        seg[v] = combine(seg[v*2],seg[v*2+1]);
		    }
		}

		void update(int v, int tl, int tr, int pos, long new_val) {
		    if (tl == tr) {
		        seg[v] = new data(new_val);
		    } else {
		        int tm = (tl + tr) / 2;
		        if (pos <= tm)
		            update(v*2, tl, tm, pos, new_val);
		        else
		            update(v*2+1, tm+1, tr, pos, new_val);
		        seg[v] = combine(seg[v*2],seg[v*2+1]);
		    }
		}
		
		data query(int v, int tl, int tr, int l, int r) {
		    if (l > r) 
		        return new data(0);
		    if (l == tl && r == tr) 
		        return seg[v];
		    int tm = (tl + tr) / 2;
		    return combine(query(v*2, tl, tm, l, min(r, tm)),query(v*2+1, tm+1, tr, max(l, tm+1), r));
		}
	}
	
	static class Bit_Tree{
		static int n;
		static int [] bit;
		
		Bit_Tree(int sz){
			Bit_Tree.n = sz;
			Bit_Tree.bit = new int[n+1];
		}
		
		static int child(int x) {
			return x + (x & (-x));
		}
		
		static int parent(int x) {
			return x - (x & (-x));
		}
		
		static void build(int [] a) {
			for(int i = 0; i<a.length; i++) {
				int start = i+1;
				while(start <= n) {
					bit[start] += a[i];
					start = child(start);
				}
			}
		}
		
		static void update(int idx,int new_val) {
			idx += 1;
			while(idx <= n) {
				bit[idx] += new_val;
				idx = child(idx);
			}
		}
		
		static int query(int right) {
			int res = 0;
			while(right > 0) {
				res += bit[right];
				right = parent(right);
			}
			return res;
		}
		
		static int query(int left,int right) {
			return query(right) - query(left-1);
		}
	}
	
	public static int gcd(int a, int b)  
    { 
        BigInteger b1 = BigInteger.valueOf(a); 
        BigInteger b2 = BigInteger.valueOf(b); 
        BigInteger gcd = b1.gcd(b2); 
            return gcd.intValue(); 
    } 
      
    public static long gcd(long a, long b)  
    { 
        BigInteger b1 = BigInteger.valueOf(a); 
        BigInteger b2 = BigInteger.valueOf(b); 
        BigInteger gcd = b1.gcd(b2); 
            return gcd.longValue(); 
    } 
}