J. Message
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

There are $$$n$$$ children sitting in a circle playing a message-passing game. The children are numbered from $$$0$$$ to $$$n-1$$$, and each of them is facing the center of the circle.

Each child holds a card. The card of the $$$i$$$-th child has a number $$$a_i$$$ on it, where $$$a_i \in \{2,3\}$$$.

If the $$$i$$$-th child receives the message, they will pass it to child number $$$(i+a_i) \bmod n$$$.

The teacher wants to inform one child such that eventually every child receives the message. Your task is to help the teacher rearrange the positions of the children and choose one child to initially receive the message. Determine whether it is possible to make sure that all children will receive the message.

Input

The first line contains a positive integer $$$T$$$ ($$$1 \le T \le 10^5$$$), representing the number of test cases.

For each test case, the first line contains a positive integer $$$n$$$ ($$$1 \le n \le 10^5$$$), representing the number of children.

The next line contains $$$n$$$ positive integers $$$a_i$$$, each being either 2 or 3, representing the number on each child's card.

It is guaranteed that $$$\sum n \le 10^6$$$.

Output

For each test case, output a line containing "Yes" or "No" indicating whether it is possible to rearrange the children such that after telling the message to one of them, every child will receive the message.

Example
Input
3
3
2 3 2
4
2 2 2 2
6
3 2 3 2 3 3
Output
Yes
No
Yes
Note

For the first test case, no rearrangement is needed; simply choosing to tell the message to the first child achieves the goal.

For the second test case, it can be proven that the goal cannot be achieved.

For the third test case, by rearranging the sequence to $$$3\ 3\ 3\ 2\ 2\ 3$$$, and telling the message to the child numbered 1, the goal can be achieved.