תן לי לשמוע את קולך, ספר לי את סיפורי מסעך —

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

Far Away Song - anemoi

תיאור הבעיה

נתונה מחרוזת $S$ באורך $n$, שהאינדקסים שלה מתחילים ב־$1$. נסמן ב־$S(i, j)=S_iS_{i+1}\cdots S_j$ את תת־המחרוזת של $S$ המורכבת מהתווים מהתו ה־$i$ ועד התו ה־$j$.

אם מחרוזת לא ריקה $B$ היא גם רישא וגם סיפא של מחרוזת $X$, ומתקיים $|B|<|X|$, אז $B$ נקראת גבול של $X$, כאשר $|X|$ מציין את אורך המחרוזת $X$.

בתחילה אתה נמצא בתת־המחרוזת $S(1, n)$. כל קפיצה מתבצעת באופן הבא:

1. בחר תת־מחרוזת $X$ מתוך תת־המחרוזת שבה אתה נמצא כעת.
2. בחר גבול $B$ של $X$, כך שמתקיים $2|B|\ge |X|$.
3. קפוץ לתת־המחרוזת המתאימה להופעה של $B$ כרישא או כסיפא של $X$, לבחירתך.

לדוגמה, כאשר $S$ היא aabaaba ואתה נמצא ב־$S(1, 7)$, תוכל לבחור $X=S(2, 7)=$ abaaba. אורכו של הגבול שלה aba הוא בדיוק מחצית מ־$|X|$, ולכן תוכל לקפוץ אל $S(2, 4)$ או אל $S(5, 7)$.

לכל $1\le i\le n$, מצא בנפרד את מספר הקפיצות המרבי שאפשר לבצע כאשר מתחילים ב־$S(1, n)$ ומגיעים בסופו של דבר אל $S(i, i)$. אם אי אפשר להגיע לשם, התשובה היא $-1$. מותר לא לבצע אף קפיצה.

ישנם מספר מקרי בדיקה.

קלט

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

לאחר מכן ניתנים מקרי הבדיקה לפי הסדר. לכל מקרה בדיקה ניתנת שורה אחת, המכילה את המחרוזת $S$.

פלט

לכל מקרה בדיקה, הדפס שורה אחת המכילה $n$ מספרים שלמים. המספר ה־$i$ הוא התשובה עבור $S(i, i)$ (אם אי אפשר להגיע אל $S(i, i)$, הדפס -1).

דוגמאות

קלט 1

5
abbababbab
bbabbaabbabbaaabab
babbaaaaabaabaaabaaba
baabaabaabaacaabaabaabaacaabaabaabaac
bbaabaaaaabbbbbbbababaabaabaabbabababbbabbabbabbba

פלט 1

-1 2 2 -1 -1 -1 2 2 -1 -1
3 3 -1 3 3 2 2 3 3 -1 3 3 2 2 2 -1 -1 -1
-1 -1 1 1 4 4 4 4 4 -1 3 3 -1 3 3 3 -1 3 3 -1 -1
-1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1 5 5 -1
1 1 2 2 -1 4 4 4 4 4 6 6 6 6 6 6 6 -1 -1 -1 -1 3 3 -1 3 3 -1 3 3 1 1 -1 -1 -1 -1 -1 2 3 3 -1 3 3 -1 3 3 -1 3 3 2 -1

הערה

במקרה הבדיקה הראשון, $S=$ abbababbab, והרישא והסיפא שלה באורך $5$ הן שתיהן abbab. אפשר לבצע שתי קפיצות באופן הבא:

• תחילה קפוץ אל $S(1, 5)$, ואז בחר $S(2, 3)=$ bb וקפוץ אל $S(2, 2)$ או אל $S(3, 3)$.
• תחילה קפוץ אל $S(6, 10)$, ואז בחר $S(7, 8)=$ bb וקפוץ אל $S(7, 7)$ או אל $S(8, 8)$.

אפשר להמשיך לקפוץ רק אם הקפיצה הראשונה היא לאחת משתי ההופעות של abbab שתוארו לעיל, והקפיצה הבאה יכולה להגיע רק לתו יחיד. לכן מספר הקפיצות המרבי לכל אחד מארבעת המיקומים האלה הוא $2$.

אי אפשר להגיע לאף אחד מהמיקומים האחרים באמצעות קפיצות, ולכן התשובה עבורם היא $-1$.

דוגמה 2

ראה את wind2.in ואת wind2.ans בקבצים המצורפים. דוגמה זו מקיימת את האילוצים של תת־משימה 3.

דוגמה 3

ראה את wind3.in ואת wind3.ans בקבצים המצורפים. דוגמה זו מקיימת את האילוצים של תת־משימה 5.

דוגמה 4

ראה את wind4.in ואת wind4.ans בקבצים המצורפים. דוגמה זו מקיימת את האילוצים של תת־משימה 6.

דוגמה 5

ראה את wind5.in ואת wind5.ans בקבצים המצורפים. דוגמה זו מקיימת את האילוצים של תת־משימה 8.

אילוצים

בבעיה זו מופעלות תלויות מתאימות בין תתי־המשימות.

תכונה מיוחדת A: קיימת מחרוזת לא ריקה $P$ כך ש־$S$ היא רישא של המחרוזת המחזורית האינסופית $P^{\infty}$, ומתקיים $|P|\le 10$.

תכונה מיוחדת B: המחרוזת $S$ נוצרת באקראי, כלומר כל תו של $S$ נבחר באקראי בהתפלגות אחידה מתוך קבוצת תווים שגודלה $\ge 2$.

תכונה מיוחדת C: לכל $1\le i<n$ מתקיים $S_i\neq S_{i+1}$.

בכל הנתונים מובטח כי $1\le n\le 2\times 10^5$, וכי סכום אורכי המחרוזות בכל מקרי הבדיקה בקובץ בדיקה יחיד מקיים $\sum n\le 2\times 10^5$. המחרוזת $S$ מכילה רק אותיות קטנות באנגלית.