Pairing like 2026 - Repovive Premier Round 1 | Repovive

2B. Pairing like 2026

1000 pts2s256 MB

You are given an integer $n$ and a string $s$ of length $2n$ consisting only of characters 0, 2, and 6.

You want to partition the positions $\{1,2,\dots,2n\}$ into exactly $n$ pairs.
That is, you must choose $n$ pairs of indices $(i,j)$ such that:

$1 \le i < j \le 2n$
every index from $1$ to $2n$ appears in exactly one pair

For each chosen pair $(i,j)$ , the two-character string $s_i s_j$ must be a substring of 2026, meaning it must be equal to one of:

20
02
26

Determine whether it is possible.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 10^5$
$|s| = 2n$
$s$ consists only of 0, 2, 6
The sum of $n$ over all test cases does not exceed $10^5$ .

Input

$t \\ \left. \begin{array}{l} n \\ s \end{array} \right\} \times t$

Output

$\left. \begin{array}{l} \text{ans} \end{array} \right\} \times t$

where $\text{ans}$ is either Yes or No.

Samples

Input

Explanation

Case 1

If we pair the indices like this, it works:

(1,2) -> "26"

Case 2

It is not possible.

Case 3

If we pair the indices like this, it works:

(1,2) -> "20", (3,4) -> "26", (5,6) -> "26"

Output

Yes
No
Yes
No
Yes

You are given an integer $n$ and a string $s$ of length $2n$ consisting only of characters 0, 2, and 6.

You want to partition the positions $\{1,2,\dots,2n\}$ into exactly $n$ pairs.
That is, you must choose $n$ pairs of indices $(i,j)$ such that:

$1 \le i < j \le 2n$
every index from $1$ to $2n$ appears in exactly one pair

For each chosen pair $(i,j)$ , the two-character string $s_i s_j$ must be a substring of 2026, meaning it must be equal to one of:

20
02
26

Determine whether it is possible.

Constraints

$1 \le t \le 10^4$
$1 \le n \le 10^5$
$|s| = 2n$
$s$ consists only of 0, 2, 6
The sum of $n$ over all test cases does not exceed $10^5$ .

$t \\ \left. \begin{array}{l} n \\ s \end{array} \right\} \times t$

$\left. \begin{array}{l} \text{ans} \end{array} \right\} \times t$

where $\text{ans}$ is either Yes or No.

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

2B. Pairing like 2026

Input

Output

Samples

2B. Pairing like 2026

Constraints

Input

Output

Samples

Constraints