A Multiple Made Only of Ones

Interview

Time limit1sMemory limit128 MB

Summary

Given n not divisible by 2 or 5, find the number of digits of the smallest repunit (all ones) that n divides.

Level: Medium5 of 10
Topics: Number theory, Math, Implementation, Hash map
Solved: No attempts yet

Problem

You are given an integer $n$ ( $1 \le n \le 10000$ ) that is divisible by neither $2$ nor $5$ . Among the numbers whose digits are all $1$ (that is, $1$ , $11$ , $111$ , $\dots$ ), you want to find one that is a multiple of $n$ . Because $n$ is not a multiple of $2$ or $5$ , such a number always exists.

Input

The input consists of several test cases. Each test case is a single line containing one integer $n$ , and the input continues until end of file.

Output

For each test case, print on its own line the number of digits of the smallest multiple of $n$ whose digits are all $1$ .

Examples6

Example 1
Input
```
3
7
9901
```
Expected output
```
3
6
12
```
Example 2
Input
```
1
```
Expected output
```
1
```
Example 3
Input
```
9
```
Expected output
```
9
```
Example 4
Input
```
11
```
Expected output
```
2
```
Example 5
Input
```
13
```
Expected output
```
6
```
Example 6
Input
```
239
```
Expected output
```
7
```