ขอให้ฉันได้ยินเสียงของเธอเถอะ เล่าเรื่องราวระหว่างการเดินทางของเธอให้ฉันฟัง—

ไม่ว่าจะเป็นเรื่องที่มีความสุข เรื่องที่เจ็บปวด หรือการพบพานเหล่านั้นที่ตราตรึงอยู่ในใจ

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$ ว่าเป็น Border ของ $X$ โดย $|X|$ หมายถึงความยาวของสตริง $X$

เริ่มต้น คุณอยู่ที่สตริงย่อย $S(1, n)$ การกระโดดแต่ละครั้งดำเนินการดังนี้:

1. เลือกสตริงย่อย $X$ ภายในสตริงย่อยที่คุณอยู่ในขณะนั้น
2. เลือก Border $B$ ของ $X$ โดยต้องมี $2|B|\ge |X|$
3. กระโดดไปยังสตริงย่อยที่ตรงกับ $B$ ซึ่งเป็นส่วนต้นหรือส่วนท้ายของ $X$ โดยเลือกอย่างใดอย่างหนึ่งได้

ตัวอย่างเช่น เมื่อ $S$ เป็น aabaaba และคุณอยู่ที่ $S(1, 7)$ คุณสามารถเลือก $X=S(2, 7)=$ abaaba ได้ Border 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$ ประกอบด้วยอักษรภาษาอังกฤษตัวพิมพ์เล็กเท่านั้น