You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

先生.B抵达华沙后，他被摩天大楼震惊了，拍了几张照片。但现在，当他看到这些照片时，他惊讶地发现，他甚至无法指出其中的建筑物数量。因此，他决定按如下方式进行处理：

• 将照片从左到右分成n个垂直部分。照片中的建筑物可以被视为矩形，其下边缘是地平线。一个建筑物可以跨越几个连续的部分，但每个部分只能包含一个可见的建筑物，或者根本没有建筑物。
• 测量该作品中每栋建筑的高度。
• 编写一个程序来计算建筑物的最小数量。 先生.B已经完成了前两个步骤，最后一个步骤来到你身边。

Format

Input

T 组测试数据，每个测试用例都以一行开头，其中包含一个整数 n （1 <= n < = 100，000）。下面是一行包含 n 个整数 - 分别是每块建筑的高度。请注意，零高度意味着这件作品中根本没有建筑物。所有输入数字都将是非负数，并且小于 1,000,000,000。

Output

对于每个测试用例，在照片中显示一行，其中包含案例编号和最小可能数量的建筑物。

输出样例的图例

Samples

2
3
1 2 3
3
1 2 1

Case 1: 3
Case 2: 2

Hint

The possible configurations of the samples are illustrated below:

Limitation

1s, 1024KiB for each test case.