Назовем строку \(t\), состоящую из символов 0 и/или 1, красивой, если количество вхождений символа 0 в этой строке не превышает \(k\), либо количество вхождений символов 1 в этой строке не превышает \(k\) (либо выполняются оба условия). Например, если \(k = 3\), строки 101010, 111, 0, 00000, 1111111000 являются красивыми, а строки 1111110000, 01010101 не являются красивыми.
Вам дана строка \(s\). Вам необходимо разбить ее на минимально возможное количество красивых строк, т. е. найти последовательность строк \(t_1, t_2, \dots, t_m\) такую, что все \(t_i\) были красивыми, \(t_1 + t_2 + \dots + t_m = s\) (где \(+\) — оператор конкатенации), а \(m\) минимально возможно.
Для каждого \(k\) от \(1\) до \(|s|\) найдите минимально возможное количество строк на которое можно разбить заданную строку \(s\) (т. е. минимально возможное \(m\) в разбиении).