Background

You are right, but simple harmonic motion is very beautiful.

However, we are not going to the sea under polygons, so you do not need to maintain the simple harmonic motion of a particle.

Problem Description

Given a digit string $S$, determine whether there exists an integer sequence $A_i$ of length $n$ where $n$ is odd, such that the values of $A_1 + A_2, A_2 + A_3, \dots, A_{n-1} + A_n, A_n + A_1$, when concatenated in this order, can form $S$.

In particular, if there is a solution such that, during concatenation, inserting $[0,\infty)$ zeros as separators between two adjacent terms can still produce $S$, then this solution is also considered valid. All testdata guarantee that $S$ has no leading $0$.

Input Format

The first line contains an integer $T$, the number of test cases.

For each test case:

The first line contains an integer $n$.

The second line contains a string $S$.

Output Format

For each test case, if a solution exists, output Yes; otherwise output No. Print each answer on its own line.

3
3
131011
1
5
3
2011

Yes
No
Yes

Hint

Sample Explanation

Explanation for the first sample:

$\begin{matrix} 7&6&4\cr +&+&+\cr 6&4&7\cr ||&||&||\cr 13&10&11\end{matrix}$

Of course, you can also say:

$\begin{matrix} 71&60&-60\cr +&+&+\cr 60&-60&71\cr ||&||&||\cr 131&0&11\end{matrix}$

The construction is not unique.

Explanation for the second sample:

If there is a solution, then $A_1 = 2.5$. But the problem states that $A$ is an integer sequence, so there is no solution.

Explanation for the third sample:

$\begin{matrix} 1&&1&0\cr +&&+&+\cr 1&&0&1\cr ||&&||&||\cr 2&0&1&1\end{matrix}$

In this solution, there are $1 \in [0,\infty)$ zeros used as separators in the middle, which meets the requirement, so output Yes.

Constraints

For $50\%$ of the testdata: $1 \le T \le 10$, $1 \le |S| \le 10$, $1 \le n \le 3$.

For $100\%$ of the testdata: $1 \le T \le 100$. It is guaranteed that $\sum n \le 10^6$ and $\sum |S| \le 10^6$, ${\tt 0} \le S_i \le {\tt 9}$, and $n$ is odd.

Translated by ChatGPT 5