Chuỗi tín hiệu

Phiên bản: Phước Hưng OJ Extended

Đề bài

Một thiết bị ghi lại chuỗi $S$ gồm $N$ chữ cái Latinh thường. Kỹ sư nghi ngờ chuỗi này được sinh ra bằng cách lặp lại liên tục một mẫu ngắn, nhưng quá trình ghi có thể dừng giữa một lần lặp của mẫu.

Một số nguyên $P$ với $1 \le P \le N$ được gọi là một chu kỳ của $S$ nếu với mọi chỉ số $i$ thỏa mãn

ta luôn có

Theo định nghĩa trên, $P=N$ luôn là một chu kỳ của $S$.

Hãy tìm chu kỳ nhỏ nhất $P$ của chuỗi $S$.

Input

• Dòng đầu chứa số nguyên $N$ — độ dài của chuỗi $S$.
• Dòng thứ hai chứa chuỗi $S$ gồm đúng $N$ chữ cái Latinh thường, không chứa dấu cách.

Output

In ra một số nguyên duy nhất $P$ — chu kỳ nhỏ nhất của chuỗi $S$.

Subtask

• Subtask 1 — 30%: $1 \le N \le 2000$.
• Subtask 3 — 70%: $1 \le N \le 10^5$.

Ví dụ

Ví dụ 1

Input

7
abababa

Output

2

Giải thích

Với $P=2$, các ký tự cách nhau $2$ vị trí tương ứng đều giống nhau:

với mọi $1 \le i \le 5$.

Không có giá trị $P=1$ thỏa mãn điều kiện, vì vậy chu kỳ nhỏ nhất của chuỗi là $2$.

Chuỗi có thể được xem như phần đầu của quá trình lặp mẫu ab:

ab ab ab a

Việc lần lặp cuối cùng chưa hoàn chỉnh vẫn phù hợp với định nghĩa của bài toán.

Ví dụ 2

Input

4
abac

Output

4

Giải thích

Các giá trị $P=1$, $P=2$ và $P=3$ đều không thỏa mãn điều kiện chu kỳ.

Trong khi đó, theo định nghĩa, $P=N=4$ luôn là một chu kỳ. Vì vậy chu kỳ nhỏ nhất của chuỗi abac là $4$.