B. Does The Universe Really Exist?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

In mathematical logic, a quantifier specifies how many elements in a domain satisfy a given property. The two most common quantifiers are the universal quantifier $$$\forall$$$, meaning "for all", and the existential quantifier $$$\exists$$$, meaning "there exists".

A universal quantifier states that a proposition must hold for every value in the domain. For example, the proposition $$$\forall x \,(x^2 \ge 0)$$$ is true over the integers because the square of every integer is non-negative. On the other hand, the proposition $$$\forall x \,(x^2 \gt x)$$$ is false over the integers, because it does not hold for certain values, such as $$$x = 0$$$ and $$$x = 1$$$.

An existential quantifier states that there exists at least one value in the domain for which the proposition holds. For example, the proposition $$$\exists x \,(x^2 - 5x + 6 = 0)$$$ is true over the integers because the equality is satisfied for $$$x = 2$$$ and $$$x = 3$$$. On the other hand, the proposition $$$\exists x \,(x^2 = 5)$$$ is false over the integers because there is no integer whose square equals $$$5$$$.

A statement may also contain multiple quantifiers. For example, the proposition $$$\forall x \, \exists y \,(x + y = 0)$$$ states that for every integer $$$x$$$, there exists an integer $$$y$$$ such that $$$x + y = 0$$$. Quantifiers are interpreted from left to right: each quantifier binds the variable that follows it, and inner quantifiers are evaluated within the scope determined by the preceding ones.

Let the domain of all variables be the set of all integers. The function $$$f(s)$$$ is defined for a binary string $$$s$$$ of length $$$n$$$. The function constructs the following proposition:

$$$$$$ \mathcal{Q}_1 x_1 \;\mathcal{Q}_2 x_2 \;\dots\; \mathcal{Q}_n x_n \;\bigl(x_1 + x_2 + \dots + x_n = 0\bigr), $$$$$$

where each $$$\mathcal{Q}_i$$$ is a quantifier determined by the $$$i$$$-th character of $$$s$$$: $$$$$$ \mathcal{Q}_i = \begin{cases} \exists & \text{if } s_i = 0, \\ \forall & \text{if } s_i = 1. \end{cases} $$$$$$

Given a binary string $$$s$$$, your task is to determine whether $$$f(s)$$$ is true or not.

Input

The first line of the input contains a single integer $$$t$$$ $$$(1 \le t \le 10^5)$$$ — the number of test cases.

The first line of each test case contains a single integer $$$n$$$ $$$(1 \le n \le 10^5)$$$ — the length of the binary string.

The second line of each test case contains a binary string $$$s$$$ of length $$$n$$$.

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

Output

For each test case, output a single string in a line — "YES" if the proposition $$$f(s)$$$ is true, and "NO" if it is not.

You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Example
Input
4
3
000
3
111
2
10
3
011
Output
YES
NO
YES
NO
Note

In the first test case, $$$s = 000$$$. The formal statement of $$$f(s)$$$ is $$$\exists x_1 \, \exists x_2 \, \exists x_3 \,(x_1 + x_2 + x_3 = 0)$$$, which in words reads: there exists an integer $$$x_1$$$ such that there exists an integer $$$x_2$$$ such that there exists an integer $$$x_3$$$ satisfying $$$x_1 + x_2 + x_3 = 0$$$. This statement is true. For example, choosing $$$(x_1, x_2, x_3) = (0,0,0)$$$ satisfies the sum.

In the second test case, $$$s = 111$$$. The formal statement of $$$f(s)$$$ is $$$\forall x_1 \, \forall x_2 \, \forall x_3 \,(x_1 + x_2 + x_3 = 0)$$$, which reads: for every integer $$$x_1$$$, for every integer $$$x_2$$$, for every integer $$$x_3$$$, the sum $$$x_1 + x_2 + x_3$$$ equals $$$0$$$. This statement is false. For instance, in the case of $$$(x_1, x_2, x_3) = (0,0,1)$$$, $$$x_1 + x_2 + x_3 = 0 + 0 + 1 = 1 \ne 0$$$.

In the third test case, $$$s = 10$$$. The formal statement of $$$f(s)$$$ is $$$\forall x_1 \, \exists x_2 \,(x_1 + x_2 = 0)$$$, which reads: for every integer $$$x_1$$$, there exists an integer $$$x_2$$$ such that $$$x_1 + x_2 = 0$$$. This statement is true. For example, if $$$x_1 = 5$$$, choosing $$$x_2 = -5$$$ satisfies the equality. Similarly, for any integer $$$x_1$$$, choosing $$$x_2 = -x_1$$$ works.