Cho một xâu ~S~ chỉ gồm các chữ cái in thường. Cách mô tả rút gọn của xâu ~S~ như sau:

• Chọn ra một xâu ~X~ ngắn nhất có thể và một số nguyên dương ~K~, sao cho khi viết xâu ~X~ lặp lại ~K~ lần thì ta thu được xâu ~S~.
• Ghép K và X, ta thu được xâu rút gọn của S.

Ví dụ:

• Xâu rút gọn của "abababab" là "4ab"
• Xâu rút gọn của "aaa" là "3a"
• Xâu rút gọn của "abac" là "1abac"

Dữ liệu:

• Gồm một dòng duy nhất chứa xâu S có độ dài không quá 1000.

Kết quả:

• In ra xâu rút gọn của xâu S.

Ví dụ:

INPUT 1

abababab

OUTPUT 1

4ab

INPUT 2

aaa

*OUTPUT2 *

3a

INPUT 3

abac

OUTPUT 3

1abac