F. Portal
time limit per test
2 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output
And thankfully, a few make sure that you get home.
— LCD Soundsystem, Home

$$$~\\$$$

Vistar finds himself trapped in a mysterious maze consisting of $$$n$$$ rooms. Surprisingly, the maze has no traditional doors — Instead, the $$$i-$$$th room contains $$$a_i$$$ portals.

Each portal is uniquely paired with exactly one other portal in the maze, forming a bidirectional connection. When Vistar enters a portal, he is instantly transported to the room of its paired portal. In particular, the portal may be paired to another portal within the same room.

Vistar begins his journey in room $$$1$$$ and aims to reach room $$$n$$$. However, the specific pairings of the portals are unknown. Your task is to determine whether Vistar can always reach the exit, regardless of how the portals are paired.

Input

The first line contains a single integer $$$T$$$ $$$(1\le T \le 10^5)$$$ — the number of test cases. For each test case:

The first line of input contains one integer $$$n$$$ $$$(1 \le n\le 10^5)$$$. The second line contains an array $$$a$$$ of length $$$n$$$ $$$(1 \le a_i\le 10^9, \sum_{i=1}^{n}a_i$$$ is even$$$)$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, output "Yes" if Vistar can always reach room $$$n$$$ or "No" if not.

You can output "Yes" and "No" in any case (for example, strings "yEs", "yes", and "YES" will be recognized as a positive response).

Example
Input
3
3
2 2 2
4
1 2 2 1
5
3 2 1 4 4
Output
No
Yes
No