KiKoS הוא מעריץ של סדרת הטלוויזיה "How I Met Your Mother". לאחרונה הוא גילה פלייליסט ב-Spotify עם הפסקול של הסדרה.

לצד הלהיטים הבלתי מעורערים "Let's Go to the Mall" ו-"Nothing Suits Me Like a Suit", הוא מצא שיר מטופש מאוד: "Bang bang bangity bang". זהו למעשה המשפט היחיד בכל השיר. כדי להאריך אותו, פשוט אומרים את אותה השורה, אך מוסיפים לפניה בהתחלה "I said", ואז אפשר לשיר את הכל שוב.

ככותב שירים מתחיל, KiKoS רוצה לעשות שימוש חוזר במבנה הזה עבור שיר חדש. באופן פורמלי, בהינתן מילה לא-ריקה $\mathbb{S}$ המורכבת מאותיות קטנות באנגלית, שיר ה-$\mathbb{S}$ מורכב מבלוק של שתי שורות שניתן לחזור עליו מספר פעמים תוך שימוש באותה מילה $\mathbb{S}$. כל בלוק נראה כך:

$$ \begin{aligned} &\mathbb{S}\texttt{, }\mathbb{S}\texttt{ }\mathbb{S}\texttt{ity }\mathbb{S} \\ &\texttt{i said }\mathbb{S}\texttt{, }\mathbb{S}\texttt{ }\mathbb{S}\texttt{ity }\mathbb{S} \end{aligned} $$

בהינתן טקסט גדול מרובה שורות, קבעו את המספר המרבי האפשרי של תווים ברצף כלשהו של בלוקים עוקבים שיוצר שיר חוקי.

קלט

הקלט מורכב ממספר שורות המכילות אותיות קטנות באנגלית, פסיקים ורווחים. כל שורה מסתיימת בתו ירידת שורה (newline). המספר הכולל של תווים, כולל תווי ירידת שורה, אינו עולה על $10^5$.

אין שורות ריקות, ושורות אינן מתחילות או מסתיימות ברווח.

פלט

הדפיסו מספר שלם יחיד: המספר המרבי האפשרי של תווים ברצף עוקב כלשהו של בלוקים התואם את תבנית השיר. מספר זה כולל את תווי ירידת השורה בסוף כל שורה ברצף, כולל השורה האחרונה של השיר. כל ירידת שורה נחשבת כתו $1$: שימו לב לכך אם אתם עובדים בסביבת Windows.

אם אין בלוקים התואמים את תבנית השיר, הדפיסו $-1$.

דוגמאות

קלט 1

bang, bang bangity bang
i said bang, bang bangity bang

פלט 1

55

קלט 2

bang, bang bangity bang
i said bang, bang bangity bang
bank, bank bankity bank
i said bank, bank bankity bank
bank, bank bankity bank
i said bank, bank bankity bank

פלט 2

110

קלט 3

grandmasters are red,
experts are blue,
parsing problems are bad,
but we believe in you

פלט 3

-1