시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 180 72 66 42.038%

문제

중간계에 살고있는 엘프 종족은 특정 숫자를 다른 숫자보다 중요하다고 믿는다. 따라서, 그들은 금속 n만큼을 이용해서 칼을 만들 때, 두께를 다음과 같은 규칙을 지키는 k로 한다면, 엄청나게 강력한 칼을 만들 수 있다고 믿는다.

음이 아닌 정수 n이 주어졌을 때, 다음과 같은 수열을 만들 수 있다.

n, 2n, 3n, 4n, ..., kn

이 때의 수열에서, 0~9까지의 숫자가 한 번 이상 나타나는 가장 작은 k를 찾아야 한다.

리븐델의 영주 엘론드는 이 일을 대신해주는 프로그램을 만드려고 한다. 금속의 양 n이 주어졌을 때, 위의 규칙을 지키는 이상적인 두께 k를 구하는 프로그램을 작성하시오.

입력

한 줄에 하나씩 n이 주어진다. n은 1보다 크거나 같고, 200,000,000보다 작거나 같은 정수이다.

출력

각 입력에 대해, 0~9까지 숫자가 모두 등장하는 가장 작은 값 k를 출력한다.

예제 입력 1

1
10
123456789
3141592

예제 출력 1

10
9
3
5
W3sicHJvYmxlbV9pZCI6IjQ0MzYiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1ZDhcdWQ1MDRcdWM3NTggXHVhYzgwIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM5MTFcdWFjMDRcdWFjYzRcdWM1ZDAgXHVjMGI0XHVhY2UwXHVjNzg4XHViMjk0IFx1YzVkOFx1ZDUwNCBcdWM4ODVcdWM4NzFcdWM3NDAgXHVkMmI5XHVjODE1IFx1YzIyYlx1Yzc5MFx1Yjk3YyZuYnNwO1x1YjJlNFx1Yjk3OCBcdWMyMmJcdWM3OTBcdWJjZjRcdWIyZTQgXHVjOTExXHVjNjk0XHVkNTU4XHViMmU0XHVhY2UwIFx1YmJmZlx1YjI5NFx1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWFkZjhcdWI0ZTRcdWM3NDAgXHVhZTA4XHVjMThkIG5cdWI5Y2NcdWQwN2NcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1Y2U3Y1x1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHViNTRjLCBcdWI0NTBcdWFlZDhcdWI5N2MgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWFkZGNcdWNlNTlcdWM3NDQgXHVjOWMwXHVkMGE0XHViMjk0IGtcdWI4NWMgXHVkNTVjXHViMmU0XHViYTc0LCBcdWM1YzRcdWNjYWRcdWIwOThcdWFjOGMgXHVhYzE1XHViODI1XHVkNTVjIFx1Y2U3Y1x1Yzc0NCBcdWI5Y2NcdWI0ZTQgXHVjMjE4IFx1Yzc4OFx1YjJlNFx1YWNlMCBcdWJiZmZcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc0Y1x1Yzc3NCBcdWM1NDRcdWIyY2MgXHVjODE1XHVjMjE4IG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWMyMThcdWM1ZjRcdWM3NDQgXHViOWNjXHViNGU0IFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPm4sIDJuLCAzbiwgNG4sIC4uLiwga248XC9wPlxyXG5cclxuPHA+XHVjNzc0IFx1YjU0Y1x1Yzc1OCBcdWMyMThcdWM1ZjRcdWM1ZDBcdWMxMWMsIDB+OVx1YWU0Y1x1YzljMFx1Yzc1OCBcdWMyMmJcdWM3OTBcdWFjMDAgXHVkNTVjIFx1YmM4OCBcdWM3NzRcdWMwYzEgXHViMDk4XHVkMGMwXHViMDk4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAga1x1Yjk3YyBcdWNjM2VcdWM1NDRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5YWNcdWJlMTBcdWIzNzhcdWM3NTggXHVjNjAxXHVjOGZjIFx1YzVkOFx1Yjg2MFx1YjRkY1x1YjI5NCBcdWM3NzQgXHVjNzdjXHVjNzQ0IFx1YjMwMFx1YzJlMFx1ZDU3NFx1YzhmY1x1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHViOWNjXHViNGRjXHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVhZTA4XHVjMThkXHVjNzU4IFx1YzU5MSBuXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzcwNFx1Yzc1OCBcdWFkZGNcdWNlNTlcdWM3NDQgXHVjOWMwXHVkMGE0XHViMjk0IFx1Yzc3NFx1YzBjMVx1YzgwMVx1Yzc3OCBcdWI0NTBcdWFlZDgga1x1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBuXHVjNzQwIDFcdWJjZjRcdWIyZTQgXHVkMDZjXHVhYzcwXHViMDk4IFx1YWMxOVx1YWNlMCwgMjAwLDAwMCwwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWM4MTVcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1Yzc4NVx1YjgyNVx1YzVkMCBcdWIzMDBcdWQ1NzQsIDB+OVx1YWU0Y1x1YzljMCBcdWMyMmJcdWM3OTBcdWFjMDAgXHViYWE4XHViNDUwIFx1YjRmMVx1YzdhNVx1ZDU1OFx1YjI5NCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YWMxMiBrXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0NDM2IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiTWFnaWMgTXVsdGlwbGUiLCJkZXNjcmlwdGlvbiI6IjxwPlRoZSBFbHZpc2ggcmFjZXMgb2YgTWlkZGxlIEVhcnRoIGJlbGlldmVkIHRoYXQgY2VydGFpbiBudW1iZXJzIHdlcmUgbW9yZSBzaWduaSBjYW50IHRoYW4gb3RoZXJzLiBXaGVuIHVzaW5nIGEgcGFydGljdWxhciBxdWFudGl0eSBuIG9mIG1ldGFsIHRvIGZvcmdlIGEgcGFydGljdWxhciBzd29yZCwgdGhleSBiZWxpZXZlZCB0aGF0IHN3b3JkIHdvdWxkIGJlIG1vc3QgcG93ZXJmdWwgaWYgdGhlIHRoaWNrbmVzcyBrIHdlcmUgY2hvc2VuIGFjY29yZGluZyB0byB0aGUgZm9sbG93aW5nIHJ1bGU6PFwvcD5cclxuXHJcbjxwPkdpdmVuIGEgbm9ubmVnYXRpdmUgaW50ZWdlciBuLCB3aGF0IGlzIHRoZSBzbWFsbGVzdCBrIHN1Y2ggdGhhdCB0aGUgZGVjaW1hbCByZXByZXNlbnRhdGlvbnMgb2YgdGhlIGludGVnZXJzIGluIHRoZSBzZXF1ZW5jZTo8XC9wPlxyXG5cclxuPHA+biwgMm4sIDNuLCA0biwgNW4sIC4uLiAsIGtuPFwvcD5cclxuXHJcbjxwPmNvbnRhaW4gYWxsIHRlbiBkaWdpdHMgKDAgdGhyb3VnaCA5KSBhdCBsZWFzdCBvbmNlPzxcL3A+XHJcblxyXG48cD5Mb3JkIEVscm9uZCBvZiBSaXZlbmRlbGwgaGFzIGNvbW1pc3Npb25lZCB5b3Ugd2l0aCB0aGUgdGFzayB0byBkZXZlbG9wIGFuIGFsZ29yaXRobSB0byBmaW5kIHRoZSBvcHRpbWFsIHRoaWNrbmVzcyAoaykgZm9yIGFueSBnaXZlbiBxdWFudGl0eSBvZiBtZXRhbCAobikuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbnB1dCB3aWxsIGNvbnNpc3Qgb2YgYSBzaW5nbGUgaW50ZWdlciBuIHBlciBsaW5lLiBUaGUgZW5kIG9mIGlucHV0IHdpbGwgYmUgc2lnbmFsZWQgYnkgZW5kIG9mIGxlLiBUaGUgaW5wdXQgaW50ZWdlciB3aWxsIGJlIGJldHdlZW4gMSBhbmQgMjAwLDAwMCwwMDAsIGluY2x1c2l2ZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5UaGUgb3V0cHV0IHdpbGwgY29uc2lzdCBvZiBhIHNpbmdsZSBpbnRlZ2VyIHBlciBsaW5lLCBpbmRpY2F0aW5nIHRoZSB2YWx1ZSBvZiBrIG5lZWRlZCBzdWNoIHRoYXQgZXZlcnkgZGlnaXQgZnJvbSAwIHRocm91Z2ggOSBpcyBzZWVuIGF0IGxlYXN0IG9uY2UuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d