Problem Description

We define the uniqueness of a sequence as the number of unique numbers in the sequence. For example, the uniqueness of $\{1,2,1,2\}$ is $0$ because there is no unique number, and the uniqueness of $\{5,6,7,6,6\}$ is $2$ because $5$ and $7$ are unique numbers.

You are given a sequence with length $N$. You need to cut it into $M$ parts (each part is a continuous subsequence), and maximize the sum of the uniqueness of the $M$ parts.

Input

There are multiple test cases.

For each test case, the first line contains $2$ integers $N$ and $M$.

The second line contains $N$ integers $A_1,A_2,\ldots,A_N$, denoting the sequence.

$1\leq M,A_i \leq N, ~ 2\leq M \leq 10$. The sum of $N$ of all the test cases is no more than $2 \cdot 10^5$.

Output

For each test case, print one integer in one line, denoting the maximal sum of the uniqueness.

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

2
1
4
4