Hamza

Interview

Time limit1sMemory limit256 MB

Summary

Find the shortest prefix of the category list that contains every distinct category appearing in the whole list.

Level: Easy3 of 10
Topics: Hash map, Array
Solved: No attempts yet

Problem

Hamza and his coach decided to practice on an online judge. The judge lists $N$ problems, and every problem belongs to exactly one category.

Hamza solves the problems in the order they are listed. He never solves problem $i$ before problem $i-1$ , because he and his coach agreed that going in order trains him on every problem, even one that is awkward to implement. His goal is to solve at least one problem from every category that exists on the judge.

You are given the category of every problem in listing order. Determine how many problems Hamza solves, counting from the first one, until he has solved at least one problem in every category on the judge.

Input

The first line contains $T$ , the number of test cases ( $1 \le T \le 100$ ).

Each test case takes two lines. The first line contains $N$ , the number of problems on the judge ( $1 \le N \le 100000$ ). The second line contains $N$ integers separated by single spaces, giving the category number of each problem from the first one to the last one. Every category number is between $1$ and $10^9$ .

Output

For each test case, print one line in the form Case n: R, where $n$ is the test case number starting from 1 and $R$ is the smallest number of problems Hamza solves from the beginning so that he has solved at least one problem in every category that appears on the judge.

Examples2

Example 1
Input
```
1
8
2 3 2 1 2 3 3 3
```
Expected output
```
Case 1: 4
```

Example 2

Input

Expected output

Case 1: 1
Case 2: 1
Case 3: 5