题目描述

给定一个长为 $n$ 的序列 $a_1, a_2,a_3, \dots ,a_n$，你需要执行 $k$ 次操作使这个序列为空。

每次操作可以执行下列内容之一：

1. 选择两个数 $i, j$，交换 $a_i, a_j$（需要满足 $1 \le i < j \le n$）。
2. 选择两个数 $i, j$，删除 $a_i,a_{i+1}, \dots ,a_j$（需要满足 $1 \le i \le j \le n$，且 $a_i = a_j$）。

请输出最小的操作数 $k$。

输入格式

第一行输入一个正整数 $T$（$1 \le T \le 5$），表示有 $T$ 个测试数据。

对于每个测试数据：

第一行输入一个正整数 $n$（$1 \le n \le 10^5$），表示序列长度为 $n$。

第二行输入 $n$ 个正整数 $a_1,a_2 \dots a_n$（$0 \le a_i \le 10^9$）。

输出格式

对于每个测试数据输出一个正整数 $k$，表示最少的操作次数。

2
5
1 2 3 2 3
3
1000000000 1000000000 99999999

2
2

提示

数据范围

对于 $100\%$ 的数据，$1\le T \le 5$，$1\le n\le 10^5$，$0\le a_i\le 10^9$。