D. Defuse the Bombs
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

The terrorists have planted some bombs in a building! Our hero, Little Horse, decides to rescue the people in the building. Unfortunately, there is more than one bomb, and Little Horse is unable to defuse all of them. To strive for more time for other people to escape, Little Horse decides to sacrifice himself.

There are $$$n$$$ bombs in the building, each of which has a countdown clock. In the beginning, the $$$i$$$-th bomb's clock is set to $$$a_i$$$. Then:

  1. Little Horse chooses one bomb, making its clock increase by $$$1$$$.
  2. Every bomb's clock decreases by $$$1$$$.
  3. If at least one clock becomes lower than $$$0$$$, all the bombs will explode. Otherwise, go back to step 1.

Obviously, the explosion is not avoidable. What a sad story. But Little Horse doesn't care about his survival now. He just wants to strive for more time. So can you tell him how many times he can do step 1 at most before the explosion?

Input

The first line of the input contains an integer $$$T$$$ ($$$1 \le T \le 100$$$) — the number of test cases.

The first line of the input contains an integer $$$n$$$ ($$$2 \le n \le 10^5$$$) — the number of bombs. The sum of $$$n$$$ will not exceed $$$3\times10^5$$$.

The next line contains $$$n$$$ numbers $$$a_1,a_2,\dots,a_n$$$ ($$$0 \le a_1,a_2,\dots,a_n \le 10^9$$$) — the clocks of the bombs in the beginning.

Output

For the $$$x$$$-th test case, if the answer is $$$y$$$, output $$$Case$$$ #$$$x$$$: $$$y$$$ in a single line.

Example
Input
2
2
1 1
3
1 2 3
Output
Case #1: 3
Case #2: 4