A. Двойное включение
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Ngọt - LẦN CUỐI (đi bên em xót xa người ơi)
ඞ

В ряд выстроены $$$n$$$ ламп с номерами от $$$1$$$ до $$$n$$$, изначально они выключены. Вы можете выполнить следующую операцию любое количество раз (возможно, ноль):

  • Выбрать две несоседние$$${}^\dagger$$$ лампы, которые в данный момент выключены, и включить их.

Определите, можете ли вы достичь конфигурации $$$s$$$, где $$$s_i = 1$$$ означает, что $$$i$$$-я лампа включена, а в противном случае $$$s_i = 0$$$.

$$${}^\dagger$$$ Соседними считаются только лампы $$$i$$$ и $$$i + 1$$$ для всех $$$1 \le i < n$$$. Обратите внимание, что лампы $$$n$$$ и $$$1$$$ не являются соседними при $$$n \ne 2$$$.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 50$$$) — количество ламп.

Вторая строка каждого набора входных данных содержит бинарную строку $$$s$$$ длины $$$n$$$ — желаемую конечную конфигурацию.

Выходные данные

Для каждого набора входных данных выведите в отдельной строке «YES», если возможно достичь конфигурацию $$$s$$$ путем применения данной операции любое количество раз. В противном случае выведите «NO».

Пример
Входные данные
5
10
1101010110
10
1001001110
6
000000
1
1
12
111111111111
Выходные данные
YES
NO
YES
NO
YES
Примечание

В первом наборе входных данных последовательность операций могла бы быть следующей (обратите внимание, что изначально все элементы $$$s$$$ равны нулю): $$$\mathtt{0000000000} \to \mathtt{\color{red}{1}0000000\color{red}{1}0} \to \mathtt{1\color{red}{1}00000\color{red}{1}10} \to \mathtt{110\color{red}{1}0\color{red}{1}0110}$$$.

В третьем наборе входных данных не нужно выполнять никаких операций.

В четвертом наборе входных данных невозможно выполнить никакую операцию, но нам нужно, чтобы горела первая лампа. Поэтому достичь желаемой конфигурации невозможно.