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:
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?
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.
For the $$$x$$$-th test case, if the answer is $$$y$$$, output $$$Case$$$ #$$$x$$$: $$$y$$$ in a single line.
2 2 1 1 3 1 2 3
Case #1: 3 Case #2: 4
Name |
---|