3. Íš zrozumiteľne?

Na Záhorí kdesi žije fena Marta (korelácia s reálnymi rozprávkami je čisto náhodná). Jej páničkovia ju kŕmia záhadnou písmenkovou polievkou. Keď Marta zje túto záhadnú polievku špecifickým spôsobom, začne rozprávať. Všetci si nad tým lámali hlavu. Po chvíli zistili, že Marta rozpráva iba vtedy keď zjedla celú polievku – ale s jedným háčikom. Musela ju jesť nasledovne: každé prehltnutie začína a končí rovnakým písmenkom. Marta je ale rýchly jedlík, tak polievku chce zjesť čo najrýchlejšie (za čo najmenej hltov). Na ďalší deň sa Marta zobudila, ale už nevedela rozprávať. Tak si šla opäť dať polievku, ale zistila, že páničkovia dnes navarili inú. Poraďte jej, ako ju najefektívnejšie zjesť tak, aby znova rozprávala.

Úloha

Máme reťazec dĺžky \(n\).

Tento reťazec musíme postupne, krok po kroku, vymazať. Mazanie funguje nasledovne:

V jednom kroku si vyberieme súvislú podpostupnosť reťazca začínajúcu a končiacu rovnakým písmenkom a zmažeme ju. Takto dokážeme vymazať aj samostatné písmenko, keďže začína a končí rovnakým písmenkom.

Nájdite minimálny počet krokov, za ktoré môžeme vymazať reťazec.

Formát vstupu

Na jedinom riadku vstupu sa nachádza reťazec \(s\) dĺžky \(n\).

\(s\) obsahuje iba veľké a malé písmenká anglickej abecedy.

Formát výstupu

Na výstup vypíšte jediné číslo - minimálny počet krokov, za ktoré môžeme vymazať reťazec.

Obmedzenia

Vstupy úlohy sú tvorené štyrmi sadami s nasledujúcimi obmedzeniami:

V prvej sade navyše platí, že \(s\) obsahuje iba písmenká a a b.

Príklady

Input:

abba

Output:

1

1. vymažeme 'a..a' -> reťazec po vymazaní : ''

Input:

abcbaccf

Output:

3

1. vymažeme 'abcba' -> reťazec po vymazaní : 'ccf'

2. vymažeme 'cc' -> reťazec po vymazaní : 'f'

3. vymažeme 'f' -> reťazec po vymazaní : ''

Input:

abacaddc

Output:

2

1. vymažeme 'aba' -> reťazec po vymazaní : 'caddc'

2. vymažeme 'caddc' -> reťazec po vymazaní : ''