Cho 2 xâu ~A~ và ~B~ chỉ gồm các kí tự Latin in thường (từ ~a~ đến ~z~).

Định nghĩa:

• ~B~ là tiền tố của ~A~, nếu như việc bỏ đi một số kí tự ở cuối xâu ~A~ (có thể không bỏ kí tự nào) sẽ thu được xâu ~B~. Ví dụ, ab, abc, abced được gọi là tiền tố của abced, nhưng abcd thì không.
• ~B~ là tiền tố thực sự của ~A~, nếu ~B~ là tiền tố của ~A~ và ~B~ khác ~A~ (tức phải bỏ đi ít nhất 1 kí tự ở ~A~).
• ~B~ là chu kì của ~A~, nếu ~B~ là tiền tố thực sự của ~A~, và ~A~ là tiền tố (không cần phải thực sự) của xâu ~B + B~ (viết liền 2 xâu ~B~ vào với nhau). Ví dụ, với xâu abababa, 2 xâu abab và ababab là chu kì của nó.
• ~B~ là chu kì dài nhất của ~A~, nếu ~B~ thỏa mãn là chu kì của ~A~ và có độ dài lớn nhất.

Nhiệm vụ của bạn là viết chương trình thực hiện:

• Đọc vào xâu ~S~
• Tính tổng độ dài các chu kì dài nhất của tất cả các tiền tố của ~S~
• Đưa kết quả ra output chuẩn

Input

• Dòng đầu tiên gồm 1 số nguyên ~k (1 \le k \le 10^6)~ là độ dài của xâu
• Dòng tiếp theo chứa xâu kí tự độ dài ~k~, các kí tự thuộc khoảng từ ~a~ đến ~z~

Output

• Đưa ra đáp số tìm được

Sample

Input #1

8
babababa

Output #1

24

Hint

Chu kì dài nhất của các tiền tố lần lượt là: (rỗng), (rỗng), ba, ba, baba, baba, bababa, bababa.

Tổng độ dài của các xâu này là 24

Problem source: Kc97ble - Free Contest 20