Lan thường đặt mật khẩu các tệp dữ liệu quan trọng. Mỗi khi gửi những tệp này cho thư ký tổng hợp, Lan chỉ gửi một chuỗi ~S~ và nhắn mật khẩu mở tệp là số lượng kí tự xuất hiện nhiều nhất trong ước của chuỗi ~S~.

Chuỗi ~X~ được gọi là ước của chuỗi ~S~ nếu chuỗi ~X~ có độ dài ngắn nhất và khi ghép một số lần liên tiếp chuỗi ~X~ ta được chuỗi ~S~. Ví dụ:

• ~S~ = aaaaa có ước là ~X~ = a;
• ~S~ = abc có ước là ~X~ = abc;
• ~S~ = ababab có ước là ~X~ = ab.

Yêu cầu: Cho một chuỗi kí tự ~S~, hãy giúp thư ký tìm ra mật khẩu mở tệp.

Dữ liệu vào

Đọc từ tệp MATKHAU.INP chỉ có một dòng duy nhất ghi chuỗi kí tự ~S~ gồm các chữ cái thường.

Kết quả

Ghi ra tệp MATKHAU.OUT một số nguyên duy nhất là mật khẩu cần tìm.

Ví dụ

Ví dụ 1

MATKHAU.INP

abaaba

MATKHAU.OUT

2

Giải thích: Chuỗi ~X~ = aba có kí tự a xuất hiện 2 lần.

Ví dụ 2

MATKHAU.INP

aaaaa

MATKHAU.OUT

1

Giới hạn

• Có 60% số điểm tương ứng với: Chuỗi ~S~ có độ dài không quá ~255~;
• Có 40% số điểm tương ứng với: Chuỗi ~S~ có độ dài không quá ~5000~.