Koko eating bananas

//Koko eating bananas

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        while(t-- > 0) {
            String line = br.readLine();
            String[] tokens = line.split(" ");
            ArrayList<Integer> array = new ArrayList<>();

            for(String token : tokens) {
                array.add(Integer.parseInt(token));
            }

            int[] arr = new int[array.size()];
            int idx = 0;

            for(int i : array) {
                arr[idx++] = i;
            }

            int k = Integer.parseInt(br.readLine());
            Solution ob = new Solution();
            int ans = ob.kokoEat(arr, k);
            System.out.println(ans);
        }
    }
}

class Solution {
    public static int kokoEat(int[] arr, int k) {
        int mx = arr[0];
        
        for(int ele: arr) {
            mx = Math.max(mx, ele);
        }
      
        int lo = 1;
        int hi = mx;
        int res = mx;

        while(lo <= hi) {
            int mid = lo + (hi - lo) / 2;

            if(check(arr, mid, k)) {
                hi = mid - 1;
                res = mid;
            }
            else {
                lo = mid + 1;
            }
        }

        return res;
    }
    
    static boolean check(int[] arr, int mid, int k) {
        int hours = 0;
        
        for(int i = 0; i < arr.length; i++) {
            hours += arr[i] / mid;
            
            if(arr[i] % mid != 0) {
                hours++;
            }
        }
        
        return hours <= k;
    }
}