Problem Setter: Tanvir Ahmed Khan

Member, IUBAT IITS Programming Club

Minion Chef has a craving for bananas. She has a collection of N piles of bananas in front of her. Each pile i (1 ≤ i ≤ N) contains A_i bananas.

Chef's mother, concerned about her health, wants her to finish eating all the bananas. She is currently out of the house and will return in H hours. Chef wants to ensure she has consumed all the bananas before her mother's return.

Chef has an eating speed of K bananas per hour. Each hour, she selects a pile of bananas. If the pile contains at least K bananas, she eats K bananas from it. Otherwise, she consumes the entire pile and stops eating for the rest of the hour.

Chef wants to eat as slowly as possible while still ensuring she finishes all the bananas before her mother returns. Help Chef determine the minimum value of K that guarantees she consumes all the bananas within H hours.

Input Format

• The first line of the input contains a single integer T denoting the number of test cases. 
• 
  
• The description of T test cases follows.

1.  The first line of each test case contains two space-separated integers N and H denoting the number of piles and the number of hours after which Chef's mom will come home.
2.  The second line contains N space-separated integers A₁, A₂, ..., A_N.

Constrains:

• 1 ≤ T ≤ 10
• 1 ≤ N ≤ 10⁵
• N ≤ H ≤ 10⁹
• 1 ≤ A_i ≤ 10⁹ for each valid i

Output Format

For each test case, print a single line containing one integer — the minimum possible value of K.

Samples