Description

身为军团指挥官，你麾下有 n 名士兵，每名士兵的战力等级为 a_i。为组建整齐划一的作战阵型，需对军团进行整编，使剩余士兵的战力等级全部相同。整编遵循以下规则：
（1）每次操作可选择一个连续的士兵队列，若队列中所有士兵的战力等级均不等于目标战力 x，则可将该队列调离阵型；
（2）目标：找到最少的操作次数，使剩余士兵的战力等级全部相同（剩余 1 名士兵也符合要求），以快速形成作战阵型。

Input

第一行输入 t（代表需要整编的军团数量）。 对于每个军团：
第一行输入 n（代表该军团的士兵数量）。
第二行输入 n 个整数 a_i（代表每名士兵的战力等级）。

Output

t 行，每行一个整数（代表对应军团整编所需的最少操作次数）。

Samples

5
3
1 1 1
5
1 2 3 4 5
5
1 2 3 2 1
7
1 2 3 1 2 3 1
13
2 2 1 2 3 3 3 2 1 2 3 1 2

0
1
1
2
3

【样例解释】

第 1 个军团：所有士兵战力均为 1，无需操作，次数为 0；
第 2 个军团：选择保留战力为 1 或 5 的士兵，只需 1 次操作移除其他连续队列；
第 3 个军团：选择保留战力为 1 的士兵，1 次操作移除中间连续队列；
第 4 个军团：选择保留战力为 1 的士兵，2 次操作移除多余连续队列；
第 5 个军团：选择保留战力为 3 的士兵，3 次操作移除多余连续队列。

【数据范围】

1 ≤ t ≤ 100
1 ≤ n ≤ 10000
1 ≤ a_i ≤ 10000