У вас есть $$$n$$$ цветочных горшков, расположенных в ряд и пронумерованных от $$$1$$$ до $$$n$$$ слева направо. Некоторые из горшков содержат цветы, в то время как другие пусты. Вам дана бинарная строка $$$s$$$, описывающая, какие горшки содержат цветы ($$$s_i = 1$$$), а какие пусты ($$$s_i = 0$$$). У вас также есть несколько кроликов, и вы хотите сделать красивую фотографию кроликов и цветов. Вы хотите посадить кроликов в каждый пустой горшок ($$$s_i = 0$$$), и для каждого кролика вы можете посадить его смотрящим либо налево, либо направо. К сожалению, кролики довольно непослушные, и они попытаются прыгнуть, что испортит фотографию.
Каждый кролик будет готовиться к прыжку в следующий горшок в том направлении, в котором он смотрит, но не будет прыгать, если в этом горшке уже есть кролик или если другой кролик готовится прыгнуть в тот же горшок с противоположной стороны. Кролики не будут прыгать за границы (кролик в горшке $$$1$$$, смотрящий налево, не будет прыгать, то же самое для кролика в горшке $$$n$$$, смотрящего направо).
Ваша цель — выбрать направления для кроликов так, чтобы они никогда не прыгнули, что позволит вам не спеша сделать фотографию. Вам нужно определить, существует ли допустимая расстановка кроликов, при которой ни один кролик никогда не прыгнет.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).
Вторая строка содержит бинарную строку $$$s$$$ длины $$$n$$$, обозначающую занятые и свободные горшки.
Гарантируется, что сумма $$$n$$$ по всем тестам не превышает $$$2 \cdot 10^5$$$.
Для каждого набора входных данных выведите «YES», если существует конфигурация кроликов, которая удовлетворяет условию, и «NO» в противном случае.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
12401003000811011011500100115010112017010101171101010511001411019001101100
YESYESNOYESYESYESYESYESYESYESNONO
В первом наборе входных данных одна из допустимых конфигураций — это посадить кролика, смотрящего направо, в позицию $$$1$$$, кролика, смотрящего налево, в позицию $$$3$$$ и кролика, смотрящего налево, в позицию $$$4$$$. Ни один кролик не будет двигаться, поскольку:
Во втором наборе входных данных одна из допустимых конфигураций — это посадить кролика, смотрящего налево, в позицию $$$1$$$, кролика, смотрящего направо, в позицию $$$2$$$ и кролика, смотрящего налево, в позицию $$$3$$$. Ни один кролик не будет двигаться, поскольку:
Можно доказать, что в третьем наборе входных данных нет допустимой расстановки кроликов.
