题目内容

装配车间里，今晚要处理的工位排成一行，一共 $m$ 个。第 $t$ 个工位待下线的零件个数是 $x_t$。

夹具每次勾取时，只能框住下标连续的一段 $[L,R]$，并且这段里各个工位的零件个数必须彼此相等，对不齐就不能勾。被勾中的工位只是零件清零，工位仍留在原处，因此左右两段不会贴合。

每个工位上的零件必须整批勾走，不能拆成两次。请给出清空整行所需的最少勾取次数。

输入描述

首行给出询问条数 $q$（$1\le q\le 10^{1}$）。

接下来 $q$ 行，每行开头是工位数 $m$（$1\le m\le 100000$），后面紧跟 $m$ 个整数 $x_1,x_2,\dots,x_m$（$1\le x_t\le 100000$）。

输出描述

把 $q$ 个答案写在同一行，两两之间用一个空格分开。从左到右第 $k$ 个数就是第 $k$ 组询问的最少勾取次数。

样例1

输入

2
7 4 4 4 1 1 9 9
4 8 8 8 8

输出

3 1

说明

• 第一组分成 $[4,4,4]$、$[1,1]$、$[9,9]$，要勾 $3$ 次。
• 第二组四个工位零件个数都是 $8$，勾 $1$ 次即可。

样例2

输入

1
6 5 5 7 7 5 5

输出

3

说明

三段是 $[5,5]$、$[7,7]$、$[5,5]$。左右两段零件个数同为 $5$，但中间隔着 $7$，工位不会贴合，不能并成一次。