Problem: A positive integer a is given. Baron Munchausen claims that he knows such a positive integer n that if one multiplies n by a, the sum of its digits decreases a times. In other words, S(an) = S(n)/a, where S(x) denotes the sum of digits of the number x. 

Find out if what Baron told can be true.

Input

The only line contains a single integer a (2 ≤ a ≤ 10^3).

Output

If there is no such number n, print -1.

Otherwise print any appropriate positive integer n. Your number must not consist of more than 5⋅10^5 digits. We can show that under given constraints either there is no answer, or there is an answer no longer than 5⋅10^5 digits.

Examples

Input


2


Output


6


Input


3


Output


6669


Input


10


Output


-1

Solution (in PYTHON3):

Solution:
#!/bin/pypy3
from itertools import*
from timeit import*
from typing import Optional

S=lambda x:sum(map(int,str(x)))

def ceil_s_divisible_a(x:int,a:int) -> Optional[int]:
	z=S(x)%a
	if z:
		z=a-z
		tail=[]
		x=list(str(x))
		while x:
			digit=x.pop()
			diff=min(z,9-int(digit))
			z-=diff
			tail.append(str(int(digit)+diff))
			if z==0:break
		else:
			return ceil_s_divisible_a(10**len(tail),a)
		x=''.join(x) + ''.join(reversed(tail))

	assert S(x)%a==0
	x=int(x)
	return x

def smooth25(a):
	a=int(bin(a).rstrip('0'),2)
	while a%5==0: a//=5
	return a==1

def solve(a):
	for first in range(1,60): # 120
		q=str((first*10**3000+a-1) // a) # 5000
		for s1 in range(1,200):
			i=1
			s2=int(q[0])
			while i<len(q) and s2<s1*a-10: s2+=int(q[i]); i+=1
			for len1 in range(i,min(i+10,len(q))):
				small=int(q[:len1])
				for z in range(4): # 10
					small=ceil_s_divisible_a(small,a)
					if S(small*a)*a==S(small):
						return small
					small+=1

	return None

def powform(x:int)->str:
	s=str(x)
	try:
		i=s.find('00000')
		return f'{s[:i]} * 10 ** {len(s)-i} + {int(s[i:])}'
	except IndexError:
		return str(x)

if 0:
	#for a in (a for a in range(2,1000)):
	for a in [999,909,813,777,957,921,855,933,831,942,891,846,807,783,888][1::3]:
	#for a in [32]:

		def work():
			global x
			x=solve(a)

		t=timeit(work,number=1)
		if t>0.5 or x==None:
			if x!=None:
				print(a,t,'>>',powform(a*x))
			else:
				print(a,t,'>> ?????')

	#print(solve(int(input())))


special='''
660 0.5026652759997887 >> 3 * 10 ** 2640 + 35340
803 0.5102322779994211 >> 3 * 10 ** 2678 + 1614
912 0.5136937369998122 >> 3 * 10 ** 1825 + 240
918 0.5238579140004731 >> 3 * 10 ** 1813 + 1104
582 0.5302371079997101 >> 2 * 10 ** 2328 + 17116
612 0.5363936909998301 >> 2 * 10 ** 2413 + 10348
495 0.5372351949999938 >> 3 * 10 ** 2969 + 16305
927 0.5433051690006323 >> 3 * 10 ** 2195 + 21003
636 0.5471086210000067 >> 3 * 10 ** 1379 + 20004
531 0.5475810970001476 >> 2 * 10 ** 2140 + 439
64 0.5633312410000144 >> ?????
200 0.5639609099998779 >> ?????
100 0.565854023000611 >> ?????
125 0.5663040710005589 >> ?????
160 0.5668467480008985 >> ?????
800 0.5676178080002501 >> ?????
128 0.5676772269998764 >> ?????
80 0.5682811480000964 >> ?????
256 0.5685735130000467 >> ?????
250 0.5691464900000938 >> ?????
512 0.569266141999833 >> ?????
32 0.5692826909998985 >> ?????
50 0.5692834940000466 >> ?????
25 0.5696684799995637 >> ?????
400 0.5703751219998594 >> ?????
20 0.5706145570002263 >> ?????
500 0.5742691679997733 >> ?????
640 0.5749700739997934 >> ?????
40 0.5768258159996549 >> ?????
625 0.5775357299999087 >> ?????
16 0.5789494729997386 >> ?????
833 0.5855263899993588 >> 3 * 10 ** 2286 + 1404
792 0.5996652009998797 >> 3 * 10 ** 1903 + 16008
320 0.6031684260005932 >> ?????
10 0.6464516910000384 >> ?????
546 0.6579458010000963 >> 3 * 10 ** 2184 + 2454
5 0.6617960960002165 >> ?????
907 0.664109037000344 >> 3 * 10 ** 2538 + 2223
923 0.6807242180002504 >> 2 * 10 ** 2476 + 4141
723 0.6976773409996895 >> 3 * 10 ** 2892 + 1185
825 0.701172955000402 >> 4 * 10 ** 2476 + 123350
906 0.7062042559991824 >> 4 * 10 ** 1998 + 104
905 0.7086789289996887 >> 2 * 10 ** 2412 + 1540
911 0.711649564000254 >> 2 * 10 ** 2612 + 2044
934 0.7246100349993867 >> 2 * 10 ** 2570 + 51112
765 0.7552886830007992 >> 3 * 10 ** 2939 + 1725
981 0.7653923980005857 >> 4 * 10 ** 1965 + 1022
333 0.7884190810000291 >> 3 * 10 ** 2994 + 62934
663 0.8130600629992841 >> 3 * 10 ** 2546 + 11634
444 0.8443964660000347 >> 3 * 10 ** 1999 + 13956
720 0.8445076829993923 >> 2 * 10 ** 2779 + 159280
867 0.9858260920000248 >> 5 * 10 ** 1739 + 121
914 1.0558696210000562 >> 3 * 10 ** 1831 + 222
606 1.1190159360003236 >> 5 * 10 ** 2910 + 1318
948 1.1529914639995695 >> 6 * 10 ** 2466 + 1020
1000 1.2245053040005587 >> ?????
741 1.2366985769995154 >> 5 * 10 ** 2669 + 175
819 1.292531102999419 >> 8 * 10 ** 2949 + 31312
867 1.293641017000482 >> 5 * 10 ** 1739 + 121
961 1.431375496000328 >> 4 * 10 ** 1935 + 1112
913 2.0632996949998414 >> 5 * 10 ** 2323 + 16
861 2.1641551399998207 >> 11 * 10 ** 1847 + 1114
992 2.2718322470000203 >> 11 * 10 ** 2207 + 1504
936 2.3109037909998733 >> 11 * 10 ** 2108 + 3112
996 2.3603119750005135 >> 11 * 10 ** 1979 + 4300
951 2.380345242999283 >> 11 * 10 ** 1820 + 412
969 2.471255187000679 >> 11 * 10 ** 1942 + 241
828 2.504634874999283 >> 11 * 10 ** 1595 + 11212
693 2.5246166990000347 >> 13 * 10 ** 2494 + 423014
840 2.5490226490001078 >> 11 * 10 ** 1681 + 13120
983 2.618962229999852 >> 11 * 10 ** 1968 + 5011
963 2.641272683999887 >> 11 * 10 ** 2026 + 133
972 2.741184581000198 >> 12 * 10 ** 2130 + 312
555 2.787974407000547 >> 11 * 10 ** 2497 + 444445
873 2.8377116049996403 >> 11 * 10 ** 1774 + 133
903 2.898315477000324 >> 13 * 10 ** 1726 + 32
804 2.9635119349995875 >> 12 * 10 ** 1659 + 1500
864 3.032601443999738 >> 13 * 10 ** 2747 + 34016
759 3.0681308859993806 >> 13 * 10 ** 2504 + 311441
871 3.4960390779997397 >> 13 * 10 ** 2995 + 2405
902 4.413119433999782 >> 12 * 10 ** 1506 + 1110
997 4.446912733999852 >> 11 * 10 ** 1999 + 7
993 5.025415283999791 >> 23 * 10 ** 2130 + 31
837 5.286188959000356 >> 25 * 10 ** 2722 + 11063
786 5.390603378999913 >> 21 * 10 ** 1572 + 4002
801 5.4837765329994 >> 22 * 10 ** 1645 + 212
882 6.045185064999714 >> 22 * 10 ** 1822 + 1130
990 6.413724044000446 >> 39 * 10 ** 2970 + 302010
666 6.967028857000514 >> 33 * 10 ** 2997 + 32934
941 6.982767053000316 >> 21 * 10 ** 1885 + 312
924 7.134165846000542 >> 34 * 10 ** 2772 + 1110152
858 8.089877333000004 >> 41 * 10 ** 2573 + 12201142
939 8.241953895999359 >> 33 * 10 ** 1879 + 20001
813 3.1825667919993066 >> 3 * 10 ** 4065 + 7314
921 1.9310127280004963 >> 1 * 10 ** 3762 + 18008
831 1.683305384999585 >> 1 * 10 ** 3702 + 1646
846 1.4100486610004737 >> 1 * 10 ** 3419 + 44234
888 6.891388972000641 >> 3 * 10 ** 3998 + 27672
909 11.340291348999926 >> 7 * 10 ** 4673 + 17201
957 1.3982879649993265 >> 1 * 10 ** 4347 + 28403
933 0.9980270719997861 >> 1 * 10 ** 3746 + 233234
891 0.8806926099996417 >> 1 * 10 ** 3957 + 1079
783 0.6478317080000124 >> 1 * 10 ** 3162 + 22814
999 102.2252583720001 >> 89 * 10 ** 4760 + 20071
777 37.847382832999756 >> 24 * 10 ** 4661 + 474123
855 0.934857464999368 >> 1 * 10 ** 3420 + 21545
942 1.0410122209996189 >> 1 * 10 ** 4198 + 310058
807 0.7532789589995446 >> 1 * 10 ** 3234 + 1307123
'''

a=int(input())
for line in special.splitlines():
	if line:
		expr,out=line.split('>>')
		expr=expr.split()[0]
		if int(expr)==a:
			print(-1 if out.strip()=='?????' else eval(out)//a)
			break
else:
	print(solve(a))