You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

注意：由于 CZOJ 评测机较慢，请使用较快的输入输出，并在提交时打开 O2 优化。

Description

那是我向往的天空之梦。

空中飘着我所仰望的 $n$ 个气球，他们排成了一排。

每个气球有一个代表颜色的整数编号 $c_i\in[1,n]$，相同颜色的编号相同。

每次操作可以选取一个区间 $[l,r]$，满足 $c_l=c_{l+1}=\cdots=c_r$，并将它们同时改为任意一个颜色 $k\in[1,n]$。

求使得所有气球颜色相同的最少操作次数。

Format

Input

第一行包含一个整数 $t$ 表示测试数据的数量。

对于每个测试数据，第一行为一个整数 $n$。

第二行包含 $n$ 个整数 $c_i$，表示第 $i$ 个气球最初的颜色。

Output

一行一个整数表示答案。

Samples

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

3
2

Limitation

对于 $20\%$ 的数据，$1\le c_i\le n\le 10$。

对于 $60\%$ 的数据，$1\le c_i\le n\le 100$。

对于 $100\%$ 的数据，$1\le c_i\le n\le 3\times10^3,1\le t\le 5$。

保证每种颜色最初出现不超过 $15$ 次。