Назовем строку $$$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$$$ в разбиении).