Để kỷ niệm ngày ~5/6/2018~ là ngày thi vào Trường THPT chuyên Lê Quý Đôn của mình, bạn Mây muốn đặt ra một bài toán nào đó có liên quan đến ngày thi. Sau một lúc suy nghĩ, Mây phát hiện ra rằng, nếu dùng số ~562018~ ghép lại với nhau một số lần sẽ được một số ~K~ là bội của một số nguyên tố ~N~ cho trước nào đó (ở đây số ~N~ khác ~2~ và ~5~; ~N~ không phải là ước của số ~562018~).

Chẳng hạn, với ~N = 3~ thì ta có thể ghép được số ~K = 562018562018562018~ là bội của ~3~.

Yêu cầu: Cho trước số nguyên tố ~N~ (~N~ khác ~2~ và ~5~; ~N~ không phải là ước của số ~562018~). Hãy tìm số lượng các chữ số của số ~K~ nhỏ nhất là bội của số ~N~ (~K~ là số tạo thành từ việc ghép số các số ~562018~ như đã nói ở trên).

Dữ liệu vào:

• Một số nguyên tố ~N (N \le 562018)~.

Dữ liệu ra:

• Một số nguyên là số lượng các chữ số của số nguyên ~K~ như đã trình bày ở trên.

Sample Input

3

Sample Output

18