最近哪吒之魔童闹海十分火爆，小劉看完回宿舍途中，看见一排相似的石墩。

题目描述

这些石墩很奇特，每个上边都有数字，然后这些数字非常有规律，每连续几个是相同的。

现在给出这些石墩上的数字 a_i ，如果连续的数字都是由一个数字复制出来的，请你求出这些数字最少由几个数字构成。

输入描述

第一行一个正整数 T ( 1 <= T <= 10³ ) 表示数据组数。

每组测试数据描述如下：

第一行一个正整数 n ( 2 <= n <= 10⁵ ), n 表示数字的数量。

第二行有 n 个正整数 a_i ( 1 <= a_i <= 10⁵ ) , a_i 表示每个整数

所有组数据 n 的之和不大于 10⁵ 。

输出描述

求出这些数字最少由几个数字构成。

样例

4
12
1 1 2 2 2 2 3 3 3 3 1 1
4
1 2 3 4
9
1 1 1 2 2 2 3 3 3
5
1 1 2 1 1

4
4
3
3