Infinite House of Pancakes (Large)

The Infinite House of Pancakes holds only finitely many pancakes, but infinitely many diners are willing to eat them. When the restaurant opens for breakfast, exactly $D$ of the infinitely many diners have pancakes on their plates, and the $i$th of them has $P_i$ pancakes. Every other diner has an empty plate.

Normally, every minute each diner with a non-empty plate eats one pancake from that plate. Some minutes are special instead. In a special minute the head server asks for the diners' attention, picks one diner whose plate is not empty, lifts some pancakes off that plate and moves them onto one other diner's plate. That other plate may be empty or non-empty. Nobody eats during a special minute, because eating then would be rude.

You are the head server on duty this morning. Deciding which minutes are special, and which pancakes move where, is your job. Every minute you either do nothing and let the diners eat, or declare a special minute, interrupt the diners and make one movement of one or more pancakes as described above.

Breakfast ends when no pancakes are left to eat. How quickly can you make that happen?

The first line contains the number of test cases $T$. $T$ test cases follow. Each test case takes two lines. The first line contains $D$, the number of diners with non-empty plates. The second line contains $D$ space separated integers giving the numbers of pancakes on those diners' plates.

Limits

• $1 \le T \le 100$
• $1 \le D \le 1000$
• $1 \le P_i \le 1000$

For each test case, print one line in the format "Case #x: y", where $x$ is the test case number starting from 1 and $y$ is the smallest number of minutes needed to finish breakfast.

In the first test case one diner starts with 3 pancakes and every other plate is empty. One optimal strategy is this.

Minute 1: do nothing. The diner eats one pancake.

Minute 2 (special): interrupt the diners and move one pancake from that diner's plate onto another diner's empty plate. However many diners start with pancakes, there are always infinitely many diners with empty plates. Nobody eats during a special minute.

Minute 3: do nothing. The two diners eat the last two pancakes, one each.

In the second test case it is optimal to let the diners eat for 2 minutes with no interruption, and all the pancakes are gone by then.

In the third test case one diner starts with 4 pancakes and every other plate is empty. It is optimal to spend the first minute as a special minute moving 2 pancakes onto another diner's empty plate, then do nothing during minutes 2 and 3 and let the diners eat.