Length of a Repunit Multiple

Time limit

Memory limit

128 MB

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.