注意：由于 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$ 次。