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

样例文件

题目描述

$n$ 个方格排成一排，第 $i$ 个方格的颜色为 $c_i$。

由若干个连续的方格组成的一段方格称作一个子段。如果一个子段中存在一个方格的颜色与该子段中其它方格的颜色均不同，则称该子段是“特色子段”。

现在让你判断这 $n$ 个方格是否满足其任意一个子段都是“特色子段”。如果满足则输出 1; 否则输出 0。

多组数据。

输入格式

第一行：一个整数 $T$，表示数据组数。

对于每组数据：

• 第一行：一个整数 $n$
• 第二行：$n$ 个整数 $c_i$

输出格式

共 $T$ 行，每组数据的答案占一行。

样例输入

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

样例输出

1
1
0

数据范围

$1 ≤ n ≤ 2×10^5, 1 ≤ T·n ≤ 2×10^6, 0 ≤ c_i ≤ 10^9$。