In the year 3018, Harry Potter is facing a fight with Lord Voldemort. Lord Voldemort has a wand that has a magical power of . Now to defeat lord Voldemort, Harry has to make a wand from spells. Harry knows number of spells but there is a problem. Each spell has a strength of magical power and lord Voldemort is knocking at the door. To defeat Voldemort, Harry has to have a more powerful wand than of his opponent. With no time in hand, Harry wants to make the wand with least number of spells, if at all possible. Now, you are Dobby, a programmer from the past 2018. Ron took you to the future and now Harry wants you to calculate the minimum number of spells he will need to defeat lord Voldemort. Can you help him?
The first line starts with the number of cases . Next test cases follow, each with two lines. First line contains the number and with a space. Following line contains integers , denoting the power of the -th spell.
Print the case number and the minimum number of spells Harry would need to make the wand. If Harry is unable to defeat Voldemort, print “Dobby is sorry for master Harry” (without the quote).
Input | Output |
---|---|
2 4 25 10 7 18 9 4 250 10 7 18 9 | Case 1: 2 Case 2: Dobby is sorry for master Harry |
In case 1, Harry can make the wand using 2 spells only: spell 1 and 3. In case 2, even if Harry uses all his four spells, he will not be able to defeat Voldemort. |