Cho xâu \(S\), tìm chu kỳ ngắn nhất của \(S\) (độ dài khác 0 nhỏ nhất sao cho \(S\) lặp lại xâu con này nhiều lần). Nếu \(S\) rỗng, in ra 0.

Đị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 chu kỳ nhỏ nhất. Nếu \(|S| = 0\) in ra 0.

Ví dụ

Input:

abcabc

Output:

3

Ràng buộc

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