Question
Ones Divisibility Quest
In a quiet town, Neha stumbled upon a curious puzzle. Her friend, Rohan, gave her a positive integer k and asked her to find the length of the smallest positive number n that is divisible by k. The catch? The number n can only contain the digit 1. If such a number exists, Neha needs to figure out its length, but if it’s impossible, she should return -1. Can you help Neha solve this tricky puzzle?
Input
The first and only line of the input contains an integer k.
Constraints
1 ≤ k ≤ 106
Constraints
1 ≤ k ≤ 106
Output
Return the length of n. If there is no such n, return -1.
Example
Sample Input
1
Sample Output
1
Explanation
The smallest answer is n = 1, which has length 1.
Sample Input
2
Sample Output
-1
Explanation
There is no such positive integer n divisible by 2.
1
Sample Output
1
Explanation
The smallest answer is n = 1, which has length 1.
Sample Input
2
Sample Output
-1
Explanation
There is no such positive integer n divisible by 2.