Description

Given a sequence of length $n$, denoted as $a_1, a_2, a_3, \dots, a_n$, you need to perform $k$ operations to make this sequence empty.

Each operation can be one of the following:

1. Select two indices $i, j$ and swap $a_i$ and $a_j$, satisfying $1 \le i < j \le n$.
2. Select two indices $i, j$ and delete the elements $a_i, a_{i+1}, \dots, a_j$, satisfying $1 \le i \le j \le n$, and $a_i = a_j$.

You should output the minimum number of operations $k$ required.

Input Format

The first line contains a positive integer $T$ ($1 \le T \le 5$), indicating the number of test cases.

For each test case:

The first line contains a positive integer $n$ ($1 \le n \le 10^5$), representing the length of the sequence.

The second line contains $n$ positive integers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le 10^9$).

Output Format

For each test case, output a single integer $k$, indicating the minimum number of operations.

2
5
1 2 3 2 3
3
1000000000 1000000000 99999999

2
2

Hint

For all the tests, $1 \le T \le 5$, $1 \le n \le 10^5$, $0 \le a_i \le 10^9$.