Background

Description

Given a string, compute recursively a new string where all the adjacent chars are now separated by a "*".

Format

Input

Output

Samples

hello

"h*e*l*l*o"

abc

"a*b*c"

ab

"a*b"

Limitation

1s, 1024KiB for each test case.