This is the hard version of this problem. The only difference is the constraint on k — the number of gifts in the offer. In this version: 2 ≤ k ≤ n.

Vasya came to the store to buy goods for his friends for the New Year. It turned out that he was very lucky — today the offer "k of goods for the price of one" is held in store.

Using this offer, Vasya can buy exactly k of any goods, paying only for the most expensive of them. Vasya decided to take this opportunity and buy as many goods as possible for his friends with the money he has.

More formally, for each good, its price is determined by a_i — the number of coins it costs. Initially, Vasya has p coins. He wants to buy the maximum number of goods. Vasya can perform one of the following operations as many times as necessary:

  * Vasya can buy one good with the index i if he currently has enough coins (i.e p ≥ a_i). After buying this good, the number of Vasya's coins will decrease by a_i, (i.e it becomes p := p - a_i). 
  * Vasya can buy a good with the index i, and also choose exactly k-1 goods, the price of which does not exceed a_i, if he currently has enough coins (i.e p ≥ a_i). Thus, he buys all these k goods, and his number of coins decreases by a_i (i.e it becomes p := p - a_i). 



Please note that each good can be bought no more than once.

For example, if the store now has n=5 goods worth a_1=2, a_2=4, a_3=3, a_4=5, a_5=7, respectively, k=2, and Vasya has 6 coins, then he can buy 3 goods. A good with the index 1 will be bought by Vasya without using the offer and he will pay 2 coins. Goods with the indices 2 and 3 Vasya will buy using the offer and he will pay 4 coins. It can be proved that Vasya can not buy more goods with six coins.

Help Vasya to find out the maximum number of goods he can buy.

Input

The first line contains one integer t (1 ≤ t ≤ 10^4) — the number of test cases in the test.

The next lines contain a description of t test cases. 

The first line of each test case contains three integers n, p, k (2 ≤ n ≤ 2 ⋅ 10^5, 1 ≤ p ≤ 2⋅10^9, 2 ≤ k ≤ n) — the number of goods in the store, the number of coins Vasya has and the number of goods that can be bought by the price of the most expensive of them.

The second line of each test case contains n integers a_i (1 ≤ a_i ≤ 10^4) — the prices of goods.

It is guaranteed that the sum of n for all test cases does not exceed 2 ⋅ 10^5.

Output

For each test case in a separate line print one integer m — the maximum number of goods that Vasya can buy.

Example

Input


8
5 6 2
2 4 3 5 7
5 11 2
2 4 3 5 7
3 2 3
4 2 6
5 2 3
10 1 3 9 2
2 10000 2
10000 10000
2 9999 2
10000 10000
4 6 4
3 2 3 2
5 5 3
1 2 2 1 2


Output


3
4
1
1
2
0
4
5

		    import java.util.*;
		    import java.math.*;
		    import java.io.*; 
		     public class A{
		     
		    static FastReader scan=new FastReader();
		     public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
		     static LinkedList<Integer>edges[];

		      //static LinkedList<Pair>edges[];
		      static boolean stdin = true;
		        static String filein = "input";
		        static String fileout = "output";
		         // FileReader scan = new FileReader("gfgInput.txt");
		    static int dx[] = { -1, 0, 1, 0 };
		    static int dy[] = { 0, 1, 0, -1 };
		    static char Dies[]={'D','L','U','R'};
		    int dx_8[]={1,1,1,0,0,-1,-1,-1};
		    int dy_8[]={-1,0,1,-1,1,-1,0,1};
		    static char sts[]={'U','R','D','L'};
		    static boolean prime[];
		    static long LCM(long a,long b){
		        return (Math.abs(a*b))/gcd(a,b);
		       }
		        public static int upperBound(long[] array, int length, long value) {
		            int low = 0;
		            int high = length;
		            while (low < high) {
		                final int mid = low+(high-low) / 2;
		                if ( array[mid]>value) {
		                    high = mid ;
		                } else {
		                    low = mid+1;
		                }
		            }
		            return low;
		        }
		       static long gcd(long a, long b) {
		        if(a!=0&&b!=0)
		            while((a%=b)!=0&&(b%=a)!=0);
		        return a^b;
		    }
		    static int countSetBits(int n) 
		        { 
		            int count = 0; 
		            while (n > 0) { 
		                if((n&1)!=1)
		                    count++;
		                //count += n & 1; 
		                n >>= 1; 
		            } 
		            return count; 
		        } 
		     static void sieve(long n) 
		        { 
		            
		            prime = new boolean[(int)n+1]; 
		            for(int i=0;i<n;i++) 
		                prime[i] = true; 
		              
		            for(int p = 2; p*p <=n; p++) 
		            { 
		               
		                if(prime[p] == true) 
		                { 
		                    
		                    for(int i = p*p; i <= n; i += p) 
		                        prime[i] = false; 
		                } 
		            } 
		        }  
		      
		     
		     
		               static boolean isprime(long x)
		               {
		                for(long i=2;i*i<=x;i++)
		                    if(x%i==0)
		                        return false;
		                    return true;
		               }
		               static int perm=0,FOR=0;
		               
		         
		     
		    static boolean flag=false;
		    static int len=100000000;
		     
		    static ArrayList<Pair>inters=new ArrayList<Pair>();
		     
		      
		    static class comp1 implements  Comparator<Pair>{  
		    public int compare(Pair o1,Pair o2){
		    return  Integer.compare((int)o2.x,(int)o1.x);
		    }
		      }
		      public static class comp2 implements Comparator<Pair>{  
		    public int compare(Pair o1,Pair o2){
		    return Integer.compare((int)o2.x,(int)o1.x); 
		    }
		      }

		     
		        static boolean isPowerOfTwo(int n)
		    {
		        if(n==0)
		        return false;
		     
		    return (int)(Math.ceil((Math.log(n) / Math.log(2)))) == 
		           (int)(Math.floor(((Math.log(n) / Math.log(2)))));
		    }
		    static ArrayList<Integer>v;
		    static ArrayList<Integer>pows;
		    static void block(long x) 
		    { 
		       v = new ArrayList<Integer>(); 
		          
		        pows=new ArrayList<Integer>();
		       
		        while (x > 0)  
		        { 
		            v.add((int)x % 2); 
		            x = x / 2; 
		        } 
		      
		        // Displaying the output when 
		        // the bit is '1' in binary 
		        // equivalent of number. 
		        for (int i = 0; i < v.size(); i++)  
		        { 
		            if (v.get(i)==1)  
		            { 
		          pows.add(i); 
		            } 
		        } 
		     
		    } 
		     
		     
		       static long ceil(long a,long b)
		       {
		        if(a%b==0)
		            return a/b;
		        return a/b+1;
		       }
		     
		     
		     
		    static boolean isprime(int n)
		        {
		            // Corner cases
		            if (n <= 1) return false;
		            if (n <= 3) return true;
		             
		            // This is checked so that we can skip
		            // middle five numbers in below loop
		            if (n % 2 == 0 || n % 3 == 0) return false;
		             
		            for (int i = 5; i * i <= n; i = i + 6)
		                if (n % i == 0 || n % (i + 2) == 0)
		                return false;
		             
		            return true;
		        }
		         
		        // Function to return the smallest
		        // prime number greater than N
		        static int nextPrime(int N)
		        {
		         
		            // Base case
		            if (N <= 1)
		                return 2;
		         
		            int prime = N;
		            boolean found = false;
		         
		            // Loop continuously until isPrime returns
		            // true for a number greater than n
		            while (!found)
		            {
		                prime++;
		         
		                if (isprime(prime))
		                    found = true;
		            }
		         
		            return prime;
		        }
		      
		        
		        static long mod=(long)1e9+7;
		     
		     
		    static long nPr(long n,long r)
		    {
		        
		        long ret=1;
		        for(long i=n-r+1;i<=n;i++)
		        {
		           ret=1L*ret*i%mod;
		               }
		        return ret%mod;
		    }
		   
		   
	

		   static int arr[];
		   static int n;
		     static final int MAXN = 2000000+5;
      
    // stores smallest prime factor for every number
    static int spf[] = new int[MAXN];
		   static void sieve()
    {
        spf[1] = 1;
        for (int i=2; i<MAXN; i++)
      
            // marking smallest prime factor for every
            // number to be itself.
            spf[i] = i;
      
        // separately marking spf for every even
        // number as 2
        for (int i=4; i<MAXN; i+=2)
            spf[i] = 2;
      
        for (int i=3; i*i<MAXN; i++)
        {
            // checking if i is prime
            if (spf[i] == i)
            {
                // marking SPF for all numbers divisible by i
                for (int j=i*i; j<MAXN; j+=i)
      
                    // marking spf[j] if it is not
                    // previously marked
                    if (spf[j]==j)
                        spf[j] = i;
            }
        }
    }
      
    // A O(log n) function returning primefactorization
    // by dividing by smallest prime factor at every step
    static ArrayList<Integer> getFactorization(int x)
    {
        ArrayList<Integer> ret = new ArrayList<>();
        while (x != 1)
        {
            ret.add(spf[x]);
            x = x / spf[x];
        }
        return ret;
    }
    static long dp[][]=new long[1006][22];
    static int m;
    static long rec(int i,int j,int arr[])
    {
    	if(j==m+1){
    		//out.println(j);
    	//	out.println(i);
    	//	for(int k=0;k<m;k++)
    	//	out.print(arr[k]+" ");
    	//	out.println();
    		return 1;
    	}
    	//out.println(i+" "+j);
    	if(dp[i][j]!=-1){
    	//	out.println(i+" "+j);
    		return dp[i][j];
    	}
    	long ret=0;
    	
    	for(int k=i;k<=n;k++)
    	{
    		arr[j]=k;
    		ret+=(rec(k,j+1,arr)%mod);
    		ret%=mod;

    	}
    	//out.println(i+" "+j);

    	return dp[i][j]=ret;
    }
		    public static void main(String[] args)  throws Exception 
		    {
		    //SUCK IT UP AND DO IT ALRIGHT
		    //scan=new FastReader("vs.txt");
		    //out = new PrintWriter("hps.out");
		   
		    int tt=1;

		  
		      
		   
		    
		     int T=tt;
		    

 tt=scan.nextInt();
		    
		    outer:while(tt-->0)
		    {
		    	int n=scan.nextInt(),p=scan.nextInt(),k=scan.nextInt();
		    	int tmp=p;
		     int arr[]=new int[n];
		     int sum=0;
		     for(int i=0;i<n;i++){
		     	arr[i]=scan.nextInt();
		     	sum+=arr[i];
		     }
		     if(p>=sum)
		     {
		     	out.println(n);
		     	continue outer;
		     }
		     Arrays.sort(arr);
		    
		     if(arr[0]>p)
		     {
		     	out.println(0);
		     	continue outer;
		     }
		     int res=0;
		     int i;
		     for( i=k-1;i<n;i+=k)
		     {
		     	if(p>=arr[i])
		     	{
		     		res+=k;
		     		p-=arr[i];
		     	}
		     	else 
		     	{
		     		for(int j=i-k+1;j<=i;j++)
		     		{
		     			if(p>=arr[j])
		     			{
		     				p-=arr[j];
		     				res++;
		     			}
		     		}
		     		break;
		     	}
		     }
		     if(res==n)
		     {
		     	out.println(n);
		     	continue outer;
		     }
		     //out.println("RES "+res+" "+i);
		     if(i>=n)
		     {
		     	i-=k;
		     	i++;
		     	//out.println(i);
		     	for(;i<n;i++)
		     	{
		     		if(p>=arr[i]){
		     			p-=arr[i];
		     			res++;
		     		}
		     	}
		     }
		     int resfin=0,res2=0;
		     p=tmp;
		     for(int l=1;l<k;l++){
		     	p=tmp;
		     	res2=0;
		     	for(i=0;i<l;i++)
		     		if(p>=arr[i]){
		     			p-=arr[i];
		     			res2++;
		     		}

		   
		     for( i=i+k-1;i<n;i+=k)
		     {
		     	if(p>=arr[i])
		     	{
		     		res2+=k;
		     		p-=arr[i];
		     	}
		     	else 
		     	{
		     		for(int j=i-k+1;j<=i;j++)
		     		{
		     			if(p>=arr[j])
		     			{
		     				p-=arr[j];
		     				res2++;
		     			}
		     		}
		     		break;
		     	}
		     }
		     if(i>=n)
		     {
		     	i-=k;
		     	i++;
		     	for(;i<n;i++)
		     	{
		     		if(p>=arr[i]){
		     			p-=arr[i];
		     			res2++;
		     		}
		     	}
		     }
		     //if(l==2)
		     //	out.println(res2);
		     resfin=Math.max(resfin,res2);
		 }
		    // out.println(res+" "+res2);
		     out.println(Math.max(resfin,res));
		      
		}
		    out.close();
		     
		    //SEE UP 
		     
		    }
		    static class special implements Comparable<special>{
		        int x,y;
		        String s;
		        special(int x,int y,String s)
		        {
		            this.x=x;
		           this.y=y;
		           this.s=s;
		        }
		     
		     @Override
		            public boolean equals(Object o){
		                if (o == this) return true;
		                if (o.getClass() != getClass()) return false;
		                special t = (special)o;
		                return t.x == x && t.y == y&&t.s.equals(s);
		            }
		     
		    public int compareTo(special o)
		    {
		        return Integer.compare(x,o.x);
		    }
		    }
		    static long binexp(long a,long n)
		    {
		        if(n==0)
		            return 1;
		        long res=binexp(a,n/2);
		        if(n%2==1)
		            return res*res*a;
		        else 
		            return res*res;
		    }
		     
		    static long powMod(long base, long exp, long mod) {
		           if (base == 0 || base == 1) return base;
		           if (exp == 0) return 1;
		           if (exp == 1) return (base % mod+mod)%mod;
		           long R = (powMod(base, exp/2, mod) % mod+mod)%mod;
		           R *= R;
		           R %= mod;
		           if ((exp & 1) == 1) {
		               return (base * R % mod+mod)%mod;
		           }
		           else return (R %mod+mod)%mod;
		       }
		    static double dis(double x1,double y1,double x2,double y2)
		    {
		        return Math.sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
		    }
		    static long mod(long x,long y)
		        {
		            if(x<0)
		                x=x+(-x/y+1)*y;
		            return x%y;
		        }
		     public static  long pow(long b, long e) {
		                long r = 1;
		                while (e > 0) {
		                    if (e % 2 == 1) r = r * b ;
		                    b = b * b;
		                    e >>= 1;
		                }
		                return r;
		            }
		    private static void sort(long[] arr) {
		            List<Long> list = new ArrayList<>();
		            for (long object : arr) list.add(object);
		            Collections.sort(list);
		        //Collections.reverse(list);
		            for (int i = 0; i < list.size(); ++i) arr[i] = list.get(i);
		        }
		    private static void sort2(int[] arr) {
		            List<Integer> list = new ArrayList<>();
		            for (int object : arr) list.add(object);
		            Collections.sort(list);
		        Collections.reverse(list);
		            for (int i = 0; i < list.size(); ++i) arr[i] = list.get(i);
		        }
		     public static class FastReader {
		            BufferedReader br;
		            StringTokenizer root;
		            
		     
		            public FastReader() {
		                br = new BufferedReader(new InputStreamReader(System.in));
		            }
		            FastReader(String filename)throws Exception
		            {
		     
		                br=new BufferedReader(new FileReader(filename));
		            }
		     
		            boolean hasNext(){
		                String line;
		                while(root.hasMoreTokens())
		                    return true;
		                return false;
		            }
		     
		            String next() {
		                while (root == null || !root.hasMoreTokens()) {
		                    try {
		                        root = new StringTokenizer(br.readLine());
		                    } catch (Exception addd) {
		                        addd.printStackTrace();
		                    }
		                }
		                return root.nextToken();
		            }
		     
		            int nextInt() {
		                return Integer.parseInt(next());
		            }
		     
		            double nextDouble() {
		                return Double.parseDouble(next());
		            }
		     
		            long nextLong() {
		                return Long.parseLong(next());
		            }
		     
		            String nextLine() {
		                String str = "";
		                try {
		                    str = br.readLine();
		                } catch (Exception addd) {
		                    addd.printStackTrace();
		                }
		                return str;
		            }
		             public int[] nextIntArray(int arraySize) {
		                int array[] = new int[arraySize];
		     
		                for (int i = 0; i < arraySize; i++) {
		                    array[i] = nextInt();
		                }
		     
		                return array;
		            }
		    }
		     static class Pair implements Comparable<Pair>{
		            public long x, y,z;
		            public Pair(long x1, long y1,long z1) {
		                x=x1;
		                y=y1;
		                z=z1;
		            }
		               public Pair(long x1, long y1) {
		                x=x1;
		                y=y1;
		            }
		            @Override
		            public int hashCode() {
		                return (int)(x + 31 * y);
		            }
		            public String toString() {
		                return x + " " + y;
		            }
		            @Override
		            public boolean equals(Object o){
		                if (o == this) return true;
		                if (o.getClass() != getClass()) return false;
		                Pair t = (Pair)o;
		                return t.x == x && t.y == y;
		            }
		    public int compareTo(Pair o)
		    {return (int)(y-o.y);
		     
		        }
		     
		    }
		     static class tuple{
		            int x,y,z;
		            tuple(int a,int b,int c){
		                x=a;
		                y=b;
		                z=c;
		            }
		        }
		        static class Edge{
		            int d,w;
		            Edge(int d,int w)
		            {
		                this.d=d;
		                this.w=w;
		            }
		        }
		    }
		     
