Any rational fraction can be represented in decimal notation. Using parentheses to denote repeating decimal digits, consider the following examples:</p>

4/2 = 2
1/4 = 0.25
10/3 = 3.(3)
1/7 = 0.(142857)
1/45 = 0.0(2)

Each of these requires a different number of characters. 4/2 = 2, so it requires only one character. 1/7 = 0.(142857), so it needs 10. Given an integer n, what is the greatest number of characters needed to represent any fraction a/b, where 1≤a,b≤n?

입력 형식

There will be several test cases in the input. Each test case will consist of a single integer n (1≤n≤500) on its own line. Input will end with a line with a single 0.

출력 형식

For each test case, output a single integer, indicating the maximum number of characters needed to represent any a/b, where 1≤a,b≤n. Output no spaces, and do not separate answers with blank lines.</p>

예제 입력

12
19
156
0

예제 출력

10
22
152