영훈이는 태형이에게 어떤 수 N과 K를 주었다.
태형이는 N을 종이에 쓰기 시작했다. 태형이는 자신이 이 수를 몇 번 써야 그 수가 K로 나누어지는지 궁금해지기 시작했다.
N=10일 때, 이 수를 한 번 쓰면 10이고, 두 번 쓰면 1010이고, 세 번쓰면 101010이고,... 이런식이다.
어떤 수 N과 K가 주어졌을 때, N을 몇 번 써야 K로 나누어 떨어지는지 구하는 프로그램을 작성하시오.
첫째 줄에 N과 K가 주어진다. N은 1,000,000,000보다 작거나 같은 자연수이다. K는 100,000보다 작거나 같은 자연수이다.
첫째 줄에 몇 번 써야하는지 그 최솟값을 출력한다. 만약 아무리 써도 불가능할 경우에는 -1을 출력한다.
n, k = map(int, input().split())
v = [0] * k
x = 10**len(str(n))
cnt = 1
res = n
while True:
tmp = n % k
if not tmp:
print(cnt)
break
else:
if v[tmp]:
print(-1)
break
else:
cnt += 1
n = tmp*x + res
v[tmp] = 1