4. Tvorba prútikov

Alchymisti už dávno vedia ako premeniť hlinu na zlato. Nerobia to, pretože by tým mohli vážne ohroziť svetové zásoby hliny (a v zlate sa zemiaky pestujú dosť ťažko). Preto legendárny alchymista Tomimos z Panopoly (skrátene Tomi) sústredil svoje úsilie na výrobu alchymistického prútika. Keď na stôl vedľa seba poukladáme zrnká zlata a zrnká hliny a mávneme prútikom, každé zrnko zlata sa premení na dve zrnká zlata a každé zrnko hliny sa premení na jedno zrnko zlata a jedno zrnko hliny. Po nejakom počte mávnutí sa prútik pokazí a bude treba zohnať ďalší.

Navyše, keď začneme s nejakou konkrétnou postupnosťou zrniek \(S\) a opakovaným mávaním prútika vyrobíme postupnosť zrniek, ktorej podúsek je \(T\), tak sa ten podúsek premení na nový prútik.

Tomiho teraz trápia otázky, či sa tento proces oplatí, po koľkých mávnutiach prútika sa mu podarí vytvoriť nový prútik, koľko zlata pri tom vyrobí, koľko hliny pri tom stratí a či postupom času mu bude počet prútikov narastať alebo klesať a hlavne, či je celý proces výhodnejší ako premena pomocou kameňa mudrcov.

Pre začiatok zistite, po koľkých mávnutiach vnikne z danej postupnosti zrniek nový alchymistický prútik.

Úloha

Zrnko zlata si označíme \(a\) (aurum) a zrnko hliny \(b\) (bahno). Potom postupnosť zrniek zodpovedá reťazcu znakov \(a,b\). Mávnutiu prútika bude zodpovedať funkcia \(p\) taká, že \(p(S)\) je reťazec písmen, ktorý vznikne z \(S\) nahradením \(a\) za \(aa\) a \(b\) za \(ab\). Napríklad \(p(\text{"abaab"}) = \text{"aaabaaaaab"}\).

\(p^k(S)\) označuje \(k\)-násobné aplikovanie funkcie \(p\) na \(S\). Presnejšie \(p^0(S)=S\) a \(p^k(S) = p^{k-1}(p(S))\). Napríklad \(p^3(\text{"b"}) = \text{"aaaaaaab"}\).

Pre dané \(S\) a \(T\) nájdite najmenšie nezáporné \(k\) také, že \(T\) je podreťazec \(p^k(S)\).

Formát vstupu

Vstup má dva riadky, na prvom je \(S\) a na druhom \(T\). Každý reťazec má dĺžku aspoň \(1\) a najviac \(200\, 000\). Oba obsahujú len písmená \(a\) a \(b\).

Formát výstupu

Vypíšte jedno celé číslo \(k\), udávajúce najmenší možný vyhovujúci počet mávnutí, alebo vypíšte \(-1\), ak žiadne vyhovujúce \(k\) neexistuje.

Príklady

Input:

b
ab

Output:

1

Input:

ababa
bab

Output:

0

Input:

a
b

Output:

-1