You are given a text. Calculate the minimum number of keystrokes needed to produce this text, if the editor described below is used.
If you haven't read the problem "Editor" before, here is a description of the functionality of the editor:

Input

The input consists of exactly ten test cases. Each test case consists of a line with at most 600 characters. The character 'd' is not used in any of the lines, but all other printable ascii characters may occur.

Output

For each test case, first print a line containing the minimum number of key strokes to produce the given line of text. In the next lines, write the keys that are pressed to produce the text. If there are several possibilities with minimum number of keystrokes, you should also minimise the number of lines, if there is still more than one possibility, minimise number of keystrokes before the first '\n', then second '\n', ...

Since 'd' is a costly operation in the editor, for each output line you should minimise the number of 'd' characters as the 2nd criterion after minimising number of keystrokes in this line.

The original input line should be the same as the output of the editor (processing the output you produce), if '\n' characters are ignored.

Notice that you have to terminate the input for the editor with two '\n'.

Example

Here only two test cases.

Input:
00001123444456789
000011234444446789

Output:
18
00d1123444456789

18
00d1123
444d6789