Under construction

Still being built. Things may change

nnnnn

Time limit2sMemory limit512 MB

Summary
Given L equal to n times the digit length of n, recover n for L up to a 10^6-digit number.
Level

Medium5 of 10

Topics
Math, Binary search, Implementation, String matching
Solved
No attempts yet

Problem

Hsara and Simone send each other messages that nobody else can read. This time Simone invented a sneaky cipher. To send Hsara a non-negative integer nn, she encrypts it as follows.

Let d(n)d(n) be the decimal expansion of nn. Write d(n)d(n) down nn times in a row and call the resulting string xx. The encryption of nn is the length of xx.

Take n=10n = 10. Then x=10101010101010101010x = 10101010101010101010, which has length 2020, so the encryption of 1010 is 2020.

For n=0n = 0 the string xx is empty, so the encryption of 00 is 00.

Hsara wrote a decryption program without any trouble. Can you?

Input

The first and only line contains an integer LL (0≤L≤101060 \le L \le 10^{10^6}), the encryption of some non-negative integer nn.

Output

Print one line containing the integer nn.

Examples1

  1. Example 1

    Input
    20
    
    Expected output
    10