Ocean View (Small)

Ocean View is a town on the edge of a small lake. The town has a single street, running west from the lake toward a hill in the east. Every house sits on one side of that street, numbered from 1 at the lakeside end up to $N$ at the foot of the hill.

Every resident wants to see the lake, but a house in front can block the view of a house behind it. House $A$ blocks the view of house $B$ when $A < B$ and the height of house $A$ is greater than or equal to the height of house $B$.

The ruler of the town has decided to destroy some houses so that every remaining house has a view of the lake. Destroying too many houses would anger the residents, so the ruler wants to destroy as few as possible.

Find the smallest number of houses that must be destroyed so that every remaining house sees the lake.

The first line contains the number of test cases $T$. Then $T$ test cases follow, each on two lines. The first line contains the number of houses $N$. The next line lists the height of each house from west to east, separated by single spaces.

Limits

• $1 \le T \le 100$
• $1 \le N \le 50$
• Each height is an integer between $1$ and $1000$, inclusive.
• The answer is always at most $4$.

For each test case, print one line in the form Case #x: y, where $x$ is the test case number starting from 1 and $y$ is the minimum number of houses that must be destroyed.

The first sample case has several answers. Keep house 1 and destroy any two of the remaining three. Destroying only the tallest house is not enough, because house 3 still blocks the view of house 4.

The second case needs no destruction at all. Every resident already sees the lake.

The third case leaves exactly one house standing. It does not matter which one.

In the fourth case, only the resident of the shortest house loses the view. Destroying the three houses west of it also works, but destroying that single house is better.