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\).