სტრინგი წარმოადგენს სასრულ მიმდევრობას ინგლისური ანბანის. ის, ასევე, შეიძლება იყოს ცარიელი მიმდევრობა, ანუ 0 ცალი ასოს მიმდევრობა. A=BC გულისხმობს, რომ A მიღებულია B-ს და C-ს კონკატენაციით (მიწებებით). სტრინგი P პრეფიქსია A-სი, თუ არსებობს სტრინგი B ისეთი, რომ A=PB. სხვა სიტყვებით რომ ვთქვათ, A-ს პრეფიქსები A-ს დასაწყისს წარმოადგენს. დამატებით, თუ P არ უდრის A-ს და P არაცარიელია, ვამბობთ, რომ P სათანადო პრეფიქსია A-სი. 

 სტრინგი Q პერიოდია A-სი, თუ Q სათანადო პრეფიქსია A-სი და A პრეფიქსია QQ-სი. მაგალითად, სტრინგები abab და ababab ორივე პერიოდია abababa-სი. მაქსიმალური პერიოდი A-სი არის ყველაზე გრძელი სტრინგი მისი პერიოდებიდან ან ცარიელი სტრინგი თუ A-ს არ გააჩნია პერიოდი. მაგალითად, მაქსიმალური პერიოდი ababab-სი არის abab, ხოლო მაქსიმალური პერიოდი abc-სი არის ცარიელი სტრინგი. 

  დაწერეთ პროგრამა, რომელიც: 

•  წაიკითხავს ინფუთიდან სტრინგის სიგრძეს და თავად სტრინგს,
•  გამოთვლის მაქსიმალური პერიოდების ჯამს ყველა შესაძლო პრეფიქსის,
•  და გამოიტანს პასუხს 

  შესატანი მონაცემები: პირველ ხაზზე რიცხვი  ( ) - სტრინგის სიგრძე. მომდევნო ხაზზე მიმდევრობა k პატარა ასოსი (lowercase) ინგლისური ანბანის, ანუ პატარა ასოებისგან შემდგარი სტრინგი. 

 გამოსატანი მონაცემები: პირველ და ერთადერთ ხაზზე თქვენმა პროგრამამ უნდა გამოიტანოს რიცხვი, რომელიც იქნება ყველა შესაძლო პრეფიქსის მაქსიმალური პერიოდების ჯამი. 

მაგალითები

შესატანი მონაცემები
8
babababa
                  დაკოპირება

გამოსატანი მონაცემები
24
                  დაკოპირება