In a strange island there are two types of beings, 1) divine, 2) evil. Divines always speak the truth, Evils always lie. Unfortunately you are in this island and you are asked to find the minimum possible number of divines in the island. It's known that there is at least one divine in the island.
So, you are walking in the island, and when you meet a person you ask him a question that 'how many divines are in the island?' since you don't know whether he is a divine or evil. And the reply is always like, 'there are at least p divines in the island.'
Now, it's also known that you always meet a new person along your path. So, your task is to find the minimum possible number of divines in the island after having the answers from all the persons in the island.
Input
Input starts with an integer T (≤ 20), denoting the number of test cases.
Each case starts with a line containing an integer n (1 ≤ n ≤ 50000), denoting the number of persons in the island. The next line contains n space separated integers between 1 and n. The ith integer in this line denotes the answer for the ith person you have met along your path.
Output
For each case, print the case number and the minimum possible number of divines in the island.
Sample
| Sample Input | Sample Output |
|---|---|
2 3 1 1 3 4 1 2 3 4 | Case 1: 2 Case 2: 1 |
Notes
- Dataset is huge, use faster I/O methods.
- For sample 1, you met three persons, two of them said 'there are at least 1 divines in the island.' And the 3rd person said, 'there are at least 3 divines in the island.' Since there is at least one divines in the island, so, the first and second persons are surely divines as they are speaking the truth. However, the 3rd person may or may not be divine. So, the minimum possible number of divines in the island is 2.