题目描述

ak机给薯条哥一个长为$n$的数组$a$,初始数组中每个数字都是白色。

薯条哥可以进行如下两种操作中的一种：

1.任选一个白色，染红

2.选择一个区间$[l,r]$,满足$a_l ≠ a_r$且区间两个端点均为白色，将区间所有元素染红

薯条哥想知道他最少几次操作可以将所有的数字染红，请你帮帮他。

输入描述

输入$2\times T+ 1$行

第一个一个正整数$T(1\le T\le 10)$ 表示测试的数据组数

接下来是每组测试数据，输入包含两行

第一行一个正整数$n(1\le n\le 10^5)$，表示数组$a$的长度

第二行$n$个正整数$a_i（1\le a_i\le 10^9）$表示$a_i$的元素

输出描述

输出包含$T$行

对于每组测试数据，输出包含一行一个正整数，表示染红所有数字的最小操作次数

样例1

输入

2
3
1 2 1
2
1 1

输出

2
2