C. ИСТИННАЯ битва
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алиса и Боб играют в игру. Имеется список из $$$n$$$ булевых значений, каждое из которых равняется либо true, либо false, заданный в виде бинарной строки$$$^{\text{∗}}$$$ длины $$$n$$$ (где $$$\texttt{1}$$$ представляет true, а $$$\texttt{0}$$$ представляет false). Изначально между булевыми значениями нет никаких операторов.

Алиса и Боб будут поочерёдно ставить между булевыми значениями операторы and (обозначающие логическое «И») и операторы or (обозначающие логическое «ИЛИ»), причём Алиса будет ходить первой. Таким образом, игра будет состоять из $$$n-1$$$ ходов, поскольку в списке $$$n$$$ булевых значений. Алиса стремится к тому, чтобы итоговое значение было равно true, а Боб — к тому, чтобы оно было равно false. По данному списку булевых значений определите, выиграет ли Алиса, если оба игрока будут играть оптимально.

Чтобы вычислить итоговое значение выражения, выполняйте следующие шаги, пока выражение не будет состоять только из одного true или false:

  • Если условие содержит операторы and, выберите любой из них и замените окружающее его подвыражение его значением.
  • В противном случае условие содержит операторы or. Выберите любой из них и замените подвыражение, окружающее оператор or, его значением.
Например, выражение true or false and false имеет значение true or (false and false) $$$=$$$ true or false $$$=$$$ true. Можно показать, что значение любого составного выражения определено однозначно.

$$$^{\text{∗}}$$$Бинарная строка — это строка, состоящая только из символов $$$\texttt{0}$$$ и $$$\texttt{1}$$$

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

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

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$) — длина строки.

Вторая строка содержит бинарную строку длины $$$n$$$, состоящую из символов $$$\texttt{0}$$$ и $$$\texttt{1}$$$ — список булевых значений.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите «YES« (без кавычек), если Алиса выиграет, и «NO» (без кавычек) в противном случае.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
5
2
11
3
010
12
101111111100
10
0111111011
8
01000010
Выходные данные
YES
NO
YES
YES
NO
Примечание

В первом наборе входных данных Алиса может поместить and между двумя булевыми значениями. Игра закончится, так как других мест для размещения операторов нет, и Алиса выиграет, потому что true and true равняется true.

Во втором наборе входных данных Алиса может поместить or между левым false и средним true. Боб может поместить and между средним true и правым false. Выражение false or true and false равняется false.

Обратите внимание, что эти примеры могут не быть оптимальными стратегиями для Алисы или Боба.