Вам задана бинарная строка \(s\), состоящая из \(n\) нулей или единиц.
Ваша задача – разделить заданную строку на минимальное число подпоследовательностей таким образом, что каждый символ строки принадлежит ровно одной подпоследовательности и каждая подпоследовательность выглядит подобно «010101 ...» или «101010 ...» (т.е. подпоследовательность не должна содержать два соседних нуля или единицы).
Напомним, что подпоследовательность — это последовательность, которая может быть получена путем удаления из заданной последовательности с помощью удаления нуля или более элементов без изменения порядка остальных элементов. Например, подпоследовательностями «1011101» являются «0», «1», «11111», «0111», «101», «1001», но не «000», «101010» и «11100».
Вам необходимо ответить на \(t\) независимых наборов тестовых данных.
Выходные данные
Для каждого набора тестовых данных выведите ответ на него: первой строкой выведите одно целое число \(k\) (\(1 \le k \le n\)) — минимальное количество подпоследовательностей, на которые вы можете разделить строку \(s\). Второй строкой выведите \(n\) целых чисел \(a_1, a_2, \dots, a_n\) (\(1 \le a_i \le k\)), где \(a_i\) — номер подпоследовательности, к которой принадлежит \(i\)-й символ строки \(s\).
Если существует несколько ответов, вы можете вывести любой.