Amazing Car Journey

You are given an amazing car with an automatic acceleration feature. On day 1, you drive a distance of \(a\) (a positive integer). On each subsequent day \(i\) (\(i \ge 2\)), you can set the car to travel an integer multiple of the previous day’s distance. In particular, on day \(i\) the distance traveled is \(r_i\) times that of day \(i-1\), where \(r_i \in \{2,3,\dots,9\}\). Thus, if on day 1 the distance is \(a\), then on day 2 it is \(a\,r_2\), on day 3 it is \(a\,r_2r_3\), and so on. The total distance traveled in \(n\) days is given by \[ S = a\Bigl(1 + r_2 + r_2r_3 + \cdots + r_2r_3\cdots r_n\Bigr). \] Given a total distance \(S\), your task is to determine the minimum number of days \(n\) (with \(n \ge 2\)) for which there exist a positive integer \(a\) and multipliers \(r_2, r_3, \dots, r_n \in \{2,3,\dots,9\}\) satisfying the above equation. If no such plan exists, output \(-1\).

inputFormat

The input consists of a single integer \(S\) representing the total distance that must be traveled.

outputFormat

Output a single integer: the minimum number of days required (which must be at least 2), or \(-1\) if it is impossible to exactly cover the distance \(S\) under the given constraints.

sample

15

2