Chu kỳ nhỏ nhất của xâu \(S\) là độ dài d nhỏ nhất sao cho S được tạo thành bằng cách lặp lại một xâu con độ dài \(d\) nhiều lần. Dùng mảng prefix function (KMP) để tìm chu kỳ nhỏ nhất.

Lưu ý: Nếu không tồn tại chu kỳ (không thể tạo bằng cách lặp), chu kỳ là chính \(|S|\).

Định dạng đầu vào

• Một dòng chứa xâu \(S\) (\(1 \le |S| \le 10^5\)), chỉ gồm chữ cái in thường.

Định dạng đầu ra

• In ra độ dài chu kỳ nhỏ nhất.

Ví dụ

Input:

abcabcabc

Output:

3

Ràng buộc

• 100% số điểm: \(|S| \le 10^5\).