Cho xâu \(S\), chu kỳ của xâu 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. Ví dụ, xâu abcabcabc có chu kỳ 3 (lặp abc 3 lần). Hãy dùng hash xâu để tìm chu kỳ nhỏ nhất.

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

• Một dòng chứa xâu \(S\) (\(1 \le |S| \le 10^5\)).

Định dạng đầu ra

• In ra độ dài chu kỳ nhỏ nhất của \(S\).

Ví dụ

Input:

abcabcabc

Output:

3

Ràng buộc

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