A Infinite Compression Plan Consortium (ICPC) desenvolveu uma nova e excelente estratégia de compressão de dados chamada «Don’t Repeat Yourself» (DRY). O DRY atua numa cadeia de caracteres e, se esta contiver duas ocorrências consecutivas da mesma subcadeia, simplesmente remove uma delas. Por exemplo, em «alfalfa seeds», pode remover uma das duas subcadeias «e» em «seeds» e uma das duas subcadeias «lfa» em «alfalfa», obtendo «alfa seds». O DRY também pode tirar partido de remoções anteriores: por exemplo, em «seventeenth baggage», remove primeiro o «e» duplicado em «seventeenth» e o «g» duplicado em «baggage», obtendo «sevententh bagage», e depois o «ent» duplicado em «sevententh» e o «ag» duplicado em «bagage», obtendo «seventh bage».

Imagem adaptada de Wikimedia Commons, domínio público

Se houver várias subcadeias consecutivas repetidas que possam ser removidas, o DRY deve escolher de modo a obter a cadeia final mais curta possível. Por exemplo, em «ABBCDCABCDCD», há duas opções: remover o «B» repetido perto do início ou o «CD» repetido no fim. Se remover o «B», poderá remover depois o «ABCDC» repetido, obtendo «ABCDCD», e finalmente remover o «CD» do fim, obtendo «ABCD». Contudo, se remover primeiro o «CD» do fim, restará «ABBCDCABCD», de onde apenas se pode remover o «B» repetido para obter «ABCDCABCD» — e desta cadeia nada mais pode ser removido. Assim, a escolha correta é começar por comprimir o «B» duplo e acabar com «ABCD».

A ICPC observou que o DRY obtém os melhores resultados em cadeias binárias, isto é, cadeias compostas apenas por zeros e uns. Por isso, encarregou-o de implementar o melhor algoritmo DRY possível para cadeias binárias. Para qualquer cadeia binária, deve apresentar uma cadeia de comprimento mínimo que se possa obter aplicando o DRY repetidamente.

Entrada

A entrada consiste numa única linha que contém uma cadeia não vazia de comprimento menor ou igual a $10^5$, composta apenas por zeros e uns.

Saída

Escreva uma linha com um resultado de comprimento mínimo da aplicação do DRY à cadeia de entrada. Se houver mais de um resultado mínimo possível, qualquer um será aceite.

Exemplos

Entrada 1

1111

Saída 1

1

Entrada 2

101

Saída 2

101

Entrada 3

10110

Saída 3

10