Ocean View

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

Every resident wants to see the lake from home. Some houses block the view of houses further east. House $A$ blocks the view of house $B$ whenever $A < B$ and house $A$ is as tall as or taller than house $B$.

Tired of the complaints about blocked views, the ruler of Ocean View decided to destroy some of the houses so that every remaining house sees the lake. Destroying too many houses would start a rebellion, so the number of destroyed houses must be as small as possible.

Find the smallest number of houses that must be destroyed so that every remaining house has an unobstructed view of the lake.

The first line contains the number of test cases $T$. The $T$ test cases follow.

Each test case consists of two lines. The first line contains the number of houses on the street, $N$. The second 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 1000$
• The height of each house is an integer between $1$ and $1000$, inclusive.

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 test case of the example has several solutions. You can keep house 1 and destroy any two of the other three. Destroying only the tallest house is not enough, because house 3 still blocks the view of house 4.

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

The third test case forces you to destroy all but one house. It does not matter which one is left standing.

In the fourth test case, the only resident complaining about a lost view lives in the shortest house. You could destroy the three houses west of it, but destroying that single house is cheaper.