Length of a Repunit Multiple

Interview

Time limit2sMemory limit128 MB

Summary

Find the minimum number of digits in a repunit (a number made only of 1s) that is divisible by a given N, or report -1 if none exists.

Level: Medium4 of 10
Topics: Math, Number theory, Simulation, BFS
Solved: No attempts yet

Problem

Given a positive integer N, consider positive integers whose every digit is 1. Among those integers, we want one that is a multiple of N.

If such a number exists, output the number of digits in the shortest one. If it does not exist, output -1.

Input

The first line contains a positive integer N.

1 <= N <= 1,000,000

Output

Output the number of digits in the shortest positive integer that is a multiple of N and whose every digit is 1. If no such integer exists, output -1.

Examples2

Example 1
Input
```
9901
```
Expected output
```
12
```
Example 2
Input
```
3
```
Expected output
```
3
```