一个广为人知的谜题是这样的：序列 1, 11, 21, 1211, 111221, 312211 中的下一个数字是什么？

答案是 13112221。其解释如下：给定一个数字，我们按照读法描述其中连续相同的数字。例如，312211 是“一个三，然后一个一，然后两个二，然后两个一”，这翻译过来就是 13112221。更正式地说，对于每一组连续相同的数字，我们写下该组的大小，紧接着写下该数字本身。例如，1111111111（十个一）被描述为 101。

给定一个数字 $x$，你需要找到该数字的最短前驱——即一个数字 $y$，使得 $y$ 在经过零次或多次上述描述操作后变为 $x$。数字的长度为其十进制表示的长度。

输入

输入文件的唯一一行包含一个不含前导零的数字 $x$。$x$ 将至少包含 $10^4$ 位数字。

输出

输出最短的前驱 $y$（不含前导零）。如果有多个可能的最短前驱，输出任意一个。注意，我们不允许前导零，因此例如 $y = 0$ 是不可能的。

样例

输入格式 1

13112221

输出格式 1

1

输入格式 2

99

输出格式 2

99