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”

Input

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

Output

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

Example

abababab 

4ab

aaa 

3a

abac 

1abac