Assignment Assignment Assignment

After the season of online classes, now it’s time for evaluation. A teacher wants to evaluate the students by giving them assignments. The teacher thinks that the best way to evaluate the students is to make them present on some topics in front of the whole class. So, he has asked you to choose the topics on which each student will present.

For convenience, the teacher has given you a list of probable topics from each chapter. But, he also gave you some conditions while choosing these topics:

• There can be more than 1 topic from each chapter.
• Each student should take at least 1 topic.
• More than one student can choose topics from a single chapter.
• One student can choose one or more topics from only one chapter. But, one topic can be covered by at most one student.
• Some topics may not be chosen. But the number of topics that are not chosen should not be very large.

As Fafa is the class representative, the teacher has asked him to provide a list of topics that each student chooses.

Now, the problem is no student wants to choose more than one topic but in that case, a lot of topics remain unassigned. Then the teacher will become very angry. Fafa and others don't want to face this situation. So they have decided that each student will choose an equal number of topics. Also, to avoid any clash, the students have agreed to assign the topics randomly satisfying all the rules stated by the teacher.

Now, Fafa is busy with writing a program that will randomly assign exact $K$ topics to each student. He has asked your help to find the optimal number $K$ that denotes the number of topics that will be assigned to each student. In other words, he asked you to find the maximum number of topic each student will choose so that the number of topics that are not chosen is as minimum as possible. It is guaranteed that each student will get at least one topic.

Input

The first line of the input will contain a single integer $T (1 \leq T \leq 15)$ that denotes the number of test cases.

For each test case, the first line will contain $2$ integers $N$ and $S (1 \leq N, S \leq 100,000)$ where $N$ denotes the number of chapters and $S$ denotes the number of students in your class.

Next line will contain $N$ space-separated integers $a_1, a_2, \dots, a_n$ where $a_i (1 \leq a_i \leq 1,000,000,000)$ denotes the number of topics from $i^{th}$ chapter. Here, $\sum_{i=1}^{n}{A_i} $ will always be greater than or equal to the number of students.

Output

For each case, print the case number and the maximum number of topics that can be assigned to each student satisfying all conditions.

Sample

Input	Output
3 3 8 2 5 1 4 2 4 3 2 1 1 4 8	Case 1: 1 Case 2: 3 Case 3: 2
For first test case, each student can take maximum 1 topics and there won't be any topic left For second test case, each student can take maximum 3 topics, one will take 3 topics from chapter 1 and another student will take 3 topics from chapter 2. Total 4 topics will be left. For third test case, 4 students each takes 2 topics and no topics will be left.