Cho một xâu S[1..n]. Ta định nghĩa một phép xoay trên S là việc chuyển kí tự đầu tiên của S về cuối xâu. Cụ thể là, sau một phép xoay thì S trở thành T = S[2..n] + S[1].

Ví dụ: S = abcaa, thì sau một phép xoay ta có S = bcaaa.

Tìm số phép xoay ít nhất để biến S thành xâu có thứ tự từ điển nhỏ nhất.

Input

Một dòng duy nhất chứa xâu S. S chỉ chứa các chữ cái in thường trong bảng chữ cái tiếng Anh (‘a’ .. ‘z’), và độ dài của S không quá 100000.

Output

Một dòng duy nhất chứa một số nguyên biểu thị số phép xoay ít nhất.

Example

Input:
mississippi

Output:
10

Bộ test và giới hạn thời gian đã được cập nhật. Một số bài đã bị "chạy quá lâu" :)