Агітації
Limits: 2 sec., 256 MiB
Перед виборами завжди є період агітації. Різні партії влаштовують мітинги на площах міст, де постійно скандують гасла. Одного передвиборчого дня Зеник вирішив прогулятися містом. Поки він гуляв центральними вулицями свого рідного міста, то чув, як звідусіль лунали різні гасла. Але він чув тільки кінцівки фраз, тобто, якщо скандували “Слава Україні!”, то Зеник міг почути “...ні” або “...країні”.
На жаль, агітатори не є дуже креативними людьми, і скандують постійно одне і те ж гасло. Проте вони є дуже наполегливими, і скандують це гасло багато разів підряд. Зенику стало цікаво, скільки ж раз вони скандували це гасло.
Вам відоме гасло p, яке скандували агітатори. Також, Вам відомий рядок r, який є конкатенацією (з’єднанням) закінчень рядка p — все те, що почув Зеник. Вам потрібно визначити, яку ж найменшу кількість разів треба було повторити гасло p, щоб Зеник почув те, що він почув.
Input
У першому рядку задано рядок p — гасло, яке скандували агітатори.
У другому рядку задано рядок r — конкатенація всього того, що почув Зеник.
Кожен рядок складається виключно з малих літер латинського алфавіту.
Output
У єдиному рядку виведіть одне ціле число — мінімальну кількість закінчень рядка p, щоб вийшов рядок r.
Гарантується, що результат завжди існує, тобто з закінчень рядка p завжди можна скласти рядок r.
Constraints
1≤|p|,|r|≤105.
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| glorytoukraine ukraineaineaine | 3 |
Notes
Зеник почув ukraine, aine,
aine.