A. А был ли массив?
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для массива целых чисел $$$a_1, a_2, \dots, a_n$$$ определим его характеристику равенства как массив $$$b_2, b_3, \dots, b_{n-1}$$$, где $$$b_i = 1$$$, если $$$i$$$-й элемент массива $$$a$$$ равен обоим своим соседям, и $$$b_i = 0$$$, если $$$i$$$-й элемент массива $$$a$$$ не равен хотя бы одному из своих соседей.

Например, для массива $$$[1, 2, 2, 2, 3, 3, 4, 4, 4, 4]$$$ характеристикой равенства будет $$$[0, 1, 0, 0, 0, 0, 1, 1]$$$.

Вам дан массив $$$b_2, b_3, \dots, b_{n-1}$$$. Ваша задача — определить, существует ли такой массив $$$a$$$, для которого заданный массив является характеристикой равенства.

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

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

Каждый набор входных данных состоит из двух строк:

  • в первой строке задано одно целое число $$$n$$$ ($$$3 \le n \le 100$$$);
  • во второй строке заданы $$$n-2$$$ целых числа $$$b_2, b_3, \dots, b_{n-1}$$$ ($$$0 \le b_i \le 1$$$).
Выходные данные

Для каждого набора входных данных выведите YES, если массив $$$a$$$ существует, или NO, если такого массива не существует. Каждую букву можно выводить в любом регистре.

Пример
Входные данные
3
10
0 1 0 0 0 0 1 1
3
1
10
0 1 0 1 1 0 0 1
Выходные данные
YES
YES
NO
Примечание

В первом примере подойдет массив $$$a = [1, 2, 2, 2, 3, 3, 4, 4, 4, 4]$$$.

Во втором примере подойдет массив $$$a = [7, 7, 7]$$$.