将大小为$$$n$$$的循环序列定义为长度为$$$n$$$的数组$$$s$$$,其中$$$s_n$$$与$$$s_1$$$相邻。
Muxii 有一个由大小为 $$$n$$$ 的循环序列 $$$a$$$ 表示的环。
然而,环本身讨厌相等的相邻元素。因此,如果序列中的两个相邻元素在任何时候相等,则其中一个将立即被删除。该序列最初不包含相等的相邻元素。
Muxii 可以执行以下操作,直到序列变空:
- 选择 $$$a$$$ 中的一个元素并将其删除。
例如,如果ring是$$$[1, 2, 4, 2, 3, 2]$$$,并且Muxii擦除元素$$$4$$$,那么ring将擦除等于$$$2$$$的元素之一,并且ring将变成$$$[1, 2, 3, 2]$$$。
Muxii 想要找到他可以执行的最大操作数。
请注意,在 $$$1$$$ 大小的环中,其唯一元素不被视为与其自身相邻(因此不会立即删除)。
输入
每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1\leq t\leq 100$$$)——测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\leq n\leq 100$$$) — 循环序列的大小。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1\leq a_i\leq n$$$) - 序列本身。
保证 $$$a_i\ne a_{i+1}$$$ 对于 $$$1\leq i<n$$$。
当$$$n>1$$$时,保证$$$a_n\ne a_1$$$。
输出
对于每个测试用例,输出一个整数 - Muxii 可以执行的最大操作数。
示例
输入 #1
3 4 1 2 3 2 4 1 2 1 2 1 1
输出 #1
4 3 1
注意
在第一个测试用例中,您可以先擦除第二个元素,然后以任意顺序逐个擦除剩余元素。总共,您可以执行操作 $$$4$$$ 次。请注意,如果先删除第一个元素,则序列将变成 $$$[2,3,2]$$$,然后立即变成 $$$[2,3]$$$。
在第二个测试用例中,可以先擦除第一个元素,然后序列变为$$$[2,1]$$$。然后您可以按任意顺序一一删除所有剩余元素。