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~.

Input

Dữ liệu đọc từ file văn bản PHNT.INP có cấu trúc như sau:

• 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~.

Output

Ghi ra file văn bản PHNT.OUT một số duy nhất là hạng của chuỗi ~S~.

Sample Input 1

3
ABC

Sample Output 1

1

Sample Input 2

5
AABAA

Sample Output 2

3

Subtask

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