B. Двоичные удаления
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задана строка $$$s$$$, состоящая только из символов '0' или '1'. Пусть $$$|s|$$$ будет длиной строки $$$s$$$.

Требуется выбрать некоторое целое число $$$k$$$ ($$$k > 0$$$) и последовательность $$$a$$$ длины $$$k$$$ такую что:

  • $$$1 \le a_1 < a_2 < \dots < a_k \le |s|$$$;
  • $$$a_{i-1} + 1 < a_i$$$ для всех $$$i$$$ от $$$2$$$ до $$$k$$$.

Символы на позициях $$$a_1, a_2, \dots, a_k$$$ удаляются, оставшиеся символы склеиваются без изменения порядка. То есть, другими словами, позиции в выбранной последовательности $$$a$$$ не должны быть соседними.

Пусть полученная строка будет $$$s'$$$. $$$s'$$$ называется отсортированной, если для всех $$$i$$$ от $$$2$$$ до $$$|s'|$$$ $$$s'_{i-1} \le s'_i$$$.

Существует ли такая последовательность $$$a$$$, что $$$s'$$$ отсортирована?

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

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

Затем следует описание $$$t$$$ наборов входных данных.

В единственной строке каждого набора входных данных содержится строка $$$s$$$ ($$$2 \le |s| \le 100$$$). Каждый символ равен либо '0', либо '1'.

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

На каждый набор входных данных выведите «YES», если существует такая последовательность $$$a$$$, что при удалении символов на позициях $$$a_1, a_2, \dots, a_k$$$ и склеивании оставшихся частей без изменения порядка получится отсортированная строка.

В противном случае выведите «NO».

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

Пример
Входные данные
5
10101011011
0000
11111
110
1100
Выходные данные
YES
YES
YES
YES
NO
Примечание

В первом наборе входных данных можно выбрать последовательность $$$a=[1,3,6,9]$$$. При удалении подчеркнутых букв из «10101011011» получится строка «0011111», которая отсортирована.

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

В четвертом наборе входных данных можно выбрать последовательность $$$a=[3]$$$. $$$s'=$$$ «11», которая отсортирована.

В пятом наборе входных данных нет способа выбрать последовательность $$$a$$$ так, чтобы $$$s'$$$ была отсортирована.