该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

给定一个长度为 $n$ 的序列 $a_1,a_2,\dots,a_n$。

你可以 恰好执行一次 操作：任选一个 非空连续区间 $[l,r]$，将该区间内的元素顺序翻转。也就是说，操作后序列变为：

定义一个位置 $i$（$1 \le i < n$）为「好位置」，当且仅当：

你的任务是求出：进行一次区间翻转后，序列中「好位置」的最大可能个数。

Input

第一行一个正整数 $T$（$1\le T\le 10^3$），表示数据组数。

对于每组数据，第一行一个整数 $n$（$1\le n\le 10^5$），表示序列长度。

第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$（$1\le a_i\le 10^9$），表示给定序列。

保证所有数据的 $n$ 之和不超过 $10^5$。

Output

对于每组数据，输出一个整数，表示恰好进行一次区间翻转后，最多能得到多少个满足 $a_i=a_{i+1}$ 的位置。

Samples

2
4
1 2 1 3
5
1 2 1 2 3

1
2

Notes

对于样例 1，选择区间 $[1,2]$ 翻转后，结果为 $2,1,1,3$，数量最多为 $1$。

对于样例 2，选择区间 $[2,3]$ 翻转后，结果为 $1,1,2,2,3$，数量最多为 $2$。