def solve(n):
	# print "solve(%d)" % n
	if n == 0:
		return -1
	if n == 1:
		return 1
	dp = [0] * n
	i = 0

	while dp[0] == 0:
		x = pow(10, i)
		# print "x == %d" % x
		xmodn = x % n		
		if xmodn == 0:
			return x
		dp1 = [0] * n
		dp1[xmodn] = x
		for j in range (n-1, -1, -1):
			dp1[j] = (dp[(j - xmodn) % n] + x) if dp[(j - xmodn) % n] != 0 else dp1[j]
			# print "dp1[%d] = %d" % (j, dp1[j])
			
		for j in range(0, n):
			dp[j] = dp1[j] if dp[j] == 0 else dp[j]
		# print dp
		i = i + 1
	
	return dp[0]

for n in range (1, 100):
	sn = solve(n)
	print "solve(%d): %d" % (n, solve(n))
	if sn % n != 0:
		print "Remainder is %d not 0" % (sn % n)

print solve(99998)