Decimal Representation Length

Time limit1sMemory limit128 MB

Summary

For each n, report the longest decimal writing among all fractions a/b with a and b from 1 to n, where the count includes digits, the point, and parentheses.

Level: Medium5 of 10
Topics: Simulation, Hash map, Brute force, Math
Solved: No attempts yet

Problem

Every rational number can be written in decimal notation. Wrapping the repeating digits in parentheses gives representations like these:

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

Each one needs a different number of characters. $4/2 = 2$ needs one character, and $1/7 = 0.(142857)$ needs 10. Count only the representation to the right of the equals sign, including the digits, the decimal point, and the parentheses. An integer value carries no decimal point, and a value that terminates carries no parentheses. Both the non-repeating prefix and the repeating block are taken as short as possible.

You are given an integer $n$ . What is the greatest number of characters needed to write a fraction $a/b$ with $1 \le a, b \le n$ this way?

Input

The input holds several test cases. Each test case is a single integer $n$ ( $1 \le n \le 500$ ) on its own line. The last line holds a single $0$ .

Output

For each test case, print one integer on its own line: the greatest number of characters needed to write $a/b$ for any $1 \le a, b \le n$ . Print no spaces and no blank lines.

Examples1

Example 1
Input
```
12
19
156
0
```
Expected output
```
10
22
152
```