URI Online Judge | 1775

Andre and the Mentos

By Mário Henrique, UFPE BR Brazil

Timelimit: 2

Andre is a programming competitor in CIn-UFPE. Every saturday, during the trainings, he eats and drinks everything: snacks, soda, cookies, water and mentos. Mainly mentos. But the problem, however, is that everytime Andre takes some candies from the tube, he has to stop coding for a while, which disturbs his concentration.

The mentos come in a tube with two heads. Each time Andre wants to take some candies, he chooses a certain flavour, and look for both heads of the tube. In each head, if there's a candy with the chosen flavour, he takes it. If there's no candy with that flavour in both heads, he takes none, and has just stopped coding for no reason. To cut his waste of time during the contest, Andre decided to minimize the amount of stops he makes to get candies. He made a fine cut along the tube to be able to see in advance which flavours and in which order the candies are inside the tube. But he's not able to get candies from the middle of the tube, since the cut he made is extremely thin and the only purpose of it is to decide better which flavours he'll take from each of the heads during his stops.

Now, Andre needs to calculate the minimum number of times he must stop coding to get his candies, following the described method, until all the candies from the tube are over. He would calculate this easily using Fourier Transform, but he is busy coding a problem. So now it's up to you, a teammate, to make a program to help him.


The first line contains an integer T (1 ≤ T ≤ 200), the number of test cases. Each test case begins with a line with an integer N, the number of mentos candies inside the tube (1 ≤ N ≤ 1000). In the next line, there are N integers, and the i-th of them is the flavour of the i-th candy in the tube. Each of these numbers is between 1 and 10⁹.


For each test case print a line with "Caso #X: Y", where X is the number of the current case, starting with 1, and Y is the minimum amount of times that Andre must stop coding to get the candies.

Input Sample Output Sample

1 3 1 3 2
1 2 3 2 1
1 1 2 3 3 4 2

Caso #1: 4
Caso #2: 3
Caso #3: 5