Cho một xâu ~S~ chỉ gồm các kí tự latin in thường. Người ta tiến hành nén xâu ~S~ như sau:

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

Ví dụ:

• Với ~S =~ abcabc thì ~T =~ abc, ~K = 2~ nên xâu nén của ~S~ là 2abc
• Với ~S =~ aaaa thì ~T =~ a, ~K = 4~ nên xâu nén của ~S~ là 4a
• Với ~S =~ freecontest thì ~T =~ freecontest, ~K = 1~ nên xâu nén của ~S~ là 1freecontest

Hãy cho biết xâu nén của ~S~.

Input

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

Output

• In ra xâu nén của xâu ~S~.

Sample

Input #1

abcabc

Output #1

2abc

Input #2

aaaa

Output #2

4a

Input #3

freecontest

Output #3

1freecontest

Problem source: Kc97ble - Free Contest