Cho số nguyên dương ~k~. Tìm số nguyên dương nhỏ nhất chỉ gồm chữ số ~1~ và chia hết cho ~k~.

Dữ liệu

Gồm một dòng duy nhất chứa một số nguyên dương ~k~ ~(1 \le k \le 10^6)~.

Kết quả

Nếu không tồn tại số thoả mãn yêu cầu đề bài, in ra ~-1~.

Ngược lại, in ra số lượng chữ số ~1~ trong số cần tìm.

Ví dụ

Sample Input 1

1

Sample Output 1

1

Sample Input 2

2

Sample Output 2

-1

Giải thích

Ở ví dụ thứ nhất, số ~1~ (có ~1~ chữ số ~1~) chia hết cho ~k = 1~.

Ở ví dụ thứ hai, tất cả các số có dạng ~11\ldots1~ đều là số lẻ, do đó không chia hết cho ~k = 2~.