Bài tập chưa có test

Một chuỗi ngọc trai ~S~ gồm ~N~ hạt được xâu lại với nhau, các hạt được đánh số từ 1 đến ~N~, mỗi hạt có một màu xác định được mã hóa bằng một chữ cái in hoa trong bảng chữ cái tiếng Anh. Hai đoạn ngọc trai trong ~S~ là giống nhau khi độ dài của chúng bằng nhau và màu của các cặp hạt tương ứng theo thứ tự xuất hiện trong hai đoạn cũng hoàn toàn giống nhau. Ví dụ hai đoạn ~AB~ và ~AB~ là giống nhau nhưng ~AB~ và ~BA~ thì không giống nhau. Hạng của chuỗi ngọc trai ~S~ là một số nguyên dương ~K~ nhỏ nhất sao cho không tồn tại hai đoạn ngọc trai bất kỳ giống nhau có độ dài ~K~.

Yêu cầu:

Hãy xác định hạng của một chuỗi ngọc trai ~S~.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên dương ~N~ là số hạt trong chuỗi ngọc trai ~S~. • Dòng thứ hai ghi ~N~ ký tự liên tiếp thể hiện lần lượt là màu của từng hạt trong ~S~.

Kết quả

Ghi ra một số duy nhất là hạng của chuỗi ~S~.

Ràng buộc

• Có 50% số điểm tương ứng với ~N ≤ 100~ • Có 30% số điểm tương ứng với ~100 < N ≤ 1000~ • Có 20% số điểm tương ứng với ~1000 < N ≤ 10^4~

Ví dụ:

Input

5
AABAA 

Output

3 

Giải thích: Chuỗi ngọc trai ~AABAA~ không thể xếp hạng 2 vì có hai đoạn ngọc trai độ dài 2 giống nhau. Tất cả các đoạn ngọc trai có độ dài 3 là: ~AAB, ABA,BAA~ chúng hoàn toàn phân biệt nên hạng của nó là 3.