Revenge of the Champernowne Constant

Time limit8sMemory limit512 MB

Summary

Given a digit string S of length up to 100, find the 1-indexed position of its first occurrence in the Champernowne constant 0.123456789101112...

Level: Hard8 of 10
Topics: String, Math, String matching, Implementation
Solved: No attempts yet

Problem

The Champernowne constant is an irrational number. After the decimal point it writes every positive integer in increasing order, one right after another, so the constant is 0.123456789101112131415... .

You are given a sequence $S$ of decimal digits. Write a program that computes the position of the first occurrence of $S$ in the digits after the decimal point. The digit right after the decimal point is position 1.

Input

The input holds several test cases. Each line contains one digit sequence. The last line of the input contains only #.

Every sequence has at least one digit and its length is at most 100.

Output

For each sequence, print the position described above as one decimal integer on its own line. You may assume every output value is less than $10^{16}$ .

Examples2

Example 1

Input

45678
67891011
21
314159265358979
#

Expected output

4
6
15
2012778692735799

Example 2
Input
```
1
#
```
Expected output
```
1
```