Zadanie

Fourierova transformácia

Počet bodov: 50

Jozef Fourier (nemýľte si ho s Josephom Fourierom) prišiel nedávno s návrhom novej transformácie na trojfarebných reťazoch (áno, aj to je odvetvie).

Trojfarebný reťazec sa skladá z písmen R, G a B. Fourierova transformácia na trojfarebnom reťazci pozostáva z vybrania si dvoch susedných znakov rôznej farby , a vymenením ich za znak farby chýbajúcej v danej dvojici. Teda reťazec RGB vieme transformovať na BB alebo RR, a BBRGRB napríklad na BGGRB, BBBRB či BBRGG.

Samozrejme, Fouriérovu transformáciu vieme potom aplikovať opakovane.

Jóžo Fourier (nemýľte si ho s Jozefom Fourierom) sa teraz snaží zistiť, aký najkratší reťazec vie získať z daného začiatočného trojfarebného reťazca opakovaným aplikovaním Fourierovej transformácie.

Táto veta je všeobecná výhovorka, prečo to musíte vlastne naprogramovať vy.

Vstup a výstup

V jedinom riadku vstupu je trojfarebný reťazec \(S\) pozostávajúci z písmen RGB. Jeho dĺžka neprekročí \(10^5\) znakov. Sú štyri sady vstupov.

V prvej sade jeho dĺžka neprekročí \(10\) znakov.

V druhej sade sa nebude vyskytovať znak \(B\).

V tretej sade jeho dĺžka neprekročí \(100\) znakov.

Vypíšte dĺžku najkratšieho reťazca, ktorý sa dá získať postupom popísaným vyššie.

Príklady

Input:

RGB

Output:

2

Input:

BBRGRB

Output:

1

BBRGRB -> BGGRB -> RGRB -> BRB -> GB -> R.