분수의 십진 표기 길이

모든 유리수는 십진 소수로 적을 수 있다. 순환하는 자리를 괄호로 묶으면 표기는 다음과 같다.

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

표기마다 필요한 글자 수가 다르다. $4/2 = 2$는 글자가 하나뿐이라 1이고, $1/7 = 0.(142857)$은 10이다. 글자 수는 등호 오른쪽 표기만 세며 숫자, 소수점, 괄호를 모두 포함한다. 값이 정수면 소수점을 찍지 않고, 순환하는 부분이 없으면 괄호도 쓰지 않는다. 순환하지 않는 앞부분과 순환 마디는 둘 다 가장 짧게 잡는다.

정수 $n$이 주어진다. $1 \le a, b \le n$인 분수 $a/b$ 하나를 이렇게 적을 때 필요한 글자 수는 최대 몇인가?

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 정수 $n$ ($1 \le n \le 500$) 하나가 한 줄에 주어진다. 마지막 줄에는 $0$ 하나가 주어진다.

각 테스트 케이스마다 $1 \le a, b \le n$인 $a/b$를 적는 데 필요한 최대 글자 수를 정수 하나로 한 줄에 출력한다. 공백과 빈 줄은 넣지 않는다.