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