Problem Description

There are $N$ balls in a row, and each ball has a color. The color of the $i$-th ball is given by a positive integer $c_i$, where the color index satisfies $1 \le c_i \le C$.

During the game, you may insert any number of balls at any positions in the current sequence. The colors of inserted balls must also be between $1$ and $C$. You may also repeatedly perform the following elimination operation: choose three consecutive balls in the current sequence; if the first ball and the third ball have the same color, you can delete these three balls at the same time. After deletion, the remaining balls on the left and right become adjacent again. Insertion operations and elimination operations can be alternated in any order.

For example, for the color sequence $1\ 2\ 1\ 3$, you can choose the first three balls $1\ 2\ 1$ and delete them, leaving the sequence $3$.

Please compute the minimum number of balls that need to be inserted so that the entire sequence can eventually be completely eliminated.

Input Format

The first line contains an integer $T$, representing the number of test cases.

For each test case:

• The first line contains two integers $N, C$, representing the initial number of balls and the number of color types.
• The second line contains $N$ integers $c_1, c_2, \dots, c_N$, representing the color of each ball in the initial sequence.

Output Format

For each test case, output one line with one integer, representing the minimum number of balls that need to be inserted.

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

2
1
3

Hint

Sample Explanation

In the first test case, you can insert two balls of color $2$, making the sequence $2\ 1\ 2\ 2\ 1\ 2$. First delete the first three balls $2\ 1\ 2$, then delete the remaining $2\ 1\ 2$, and the whole sequence can be eliminated. Therefore, the answer is $2$.

In the second test case, you can first delete the middle $2\ 3\ 2$, leaving $1\ 1$. Then insert one ball of color $2$ to get $1\ 2\ 1$ and delete it. Therefore, the answer is $1$.

In the third test case, at least $3$ balls need to be inserted. For example, first insert two balls of color $1$ to form $1\ 1\ 1$ and delete it, leaving $2\ 3$; then insert one ball of color $2$ to form $2\ 3\ 2$ and delete it.

Constraints

For $30\%$ of the testdata, $N \le 15$.

For all testdata, $T \le 20$, $1 \le N \le 300$, $1 \le C \le 10$, $1 \le c_i \le C$.

Translated by ChatGPT 5