题目描述

给你一个长度为$\red{n}$的数组$\red{a_0,a_1,...,a_{n-1}，}$其中$\red{a_i∈}$$\red{\{0,1,2\}}$。

给出下述一种操作：

选择一个下标$\red{i}$满足$\red{(a_i+1)~mod~3=a_{(i+1)~mod~ n}，}$那么就令$\red{a_i⬅(a_i+1)~mod~3.}$

那么经过若干次操作之后（可以不进行操作）能否使得所有的元素相等呢？

输入格式

包含多组输入输出，第一行包含一个整数$\red{T}$表示输入的组数；

对于每一组输入，第一行包含一个整数$\red{n，}$

第二行包含$\red{n}$个整数$\red{a_0,a_1,...,a_{n-1}}$；

输出格式

对于每组输入，输出一行表示答案，如果可能，则输出"$\red{Yes}$"；否则输出"$\red{No}$"。

样例

输入样例

5
2
1 0
3
0 2 1
4
0 1 2 2
5
0 2 1 0 1
6
2 0 2 1 0 1

输出样例

Yes
No
Yes
No
Yes

提示

对于$\red{100\%}$的数据，$\red{1<=T<=10^5,2<=n<=10^6,0<=a_i<3}$且多组输入的$\red{n}$的总和不超过$\red{10^6}$

其中$\red{20\%}$的数据， $\red{1<=T<=10,n<=10}$