시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 192 81 74 44.048%

문제

중간계에 살고있는 엘프 종족은 특정 숫자를 다른 숫자보다 중요하다고 믿는다. 따라서, 그들은 금속 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+XHVjNzc0XHViNTRjXHVjNzU4IFx1YzIxOFx1YzVmNFx1YzVkMFx1YzExYywgMH45XHVhZTRjXHVjOWMwXHVjNzU4IFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWQ1NWMgXHViYzg4IFx1Yzc3NFx1YzBjMSBcdWIwOThcdWQwYzBcdWIwOThcdWIyOTQgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBrXHViOTdjIFx1Y2MzZVx1YzU0NFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjlhY1x1YmUxMFx1YjM3OFx1Yzc1OCBcdWM2MDFcdWM4ZmMgXHVjNWQ4XHViODYwXHViNGRjXHViMjk0IFx1Yzc3NCBcdWM3N2NcdWM3NDQgXHViMzAwXHVjMmUwXHVkNTc0XHVjOGZjXHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWI5Y2NcdWI0ZGNcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWFlMDhcdWMxOGRcdWM3NTggXHVjNTkxIG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjNzA0XHVjNzU4IFx1YWRkY1x1Y2U1OVx1Yzc0NCBcdWM5YzBcdWQwYTRcdWIyOTQgXHVjNzc0XHVjMGMxXHVjODAxXHVjNzc4IFx1YjQ1MFx1YWVkOCBrXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1Mjkgblx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIG5cdWM3NDAgMVx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCAyMDAsMDAwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVjNzg1XHViODI1XHVjNWQwIFx1YjMwMFx1ZDU3NCwgMH45XHVhZTRjXHVjOWMwIFx1YzIyYlx1Yzc5MFx1YWMwMCBcdWJhYThcdWI0NTAgXHViNGYxXHVjN2E1XHVkNTU4XHViMjk0IFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVhYzEyIGtcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQ0MzYiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNYWdpYyBNdWx0aXBsZSIsImRlc2NyaXB0aW9uIjoiPHA+VGhlIEVsdmlzaCByYWNlcyBvZiBNaWRkbGUgRWFydGggYmVsaWV2ZWQgdGhhdCBjZXJ0YWluIG51bWJlcnMgd2VyZSBtb3JlIHNpZ25pIGNhbnQgdGhhbiBvdGhlcnMuIFdoZW4gdXNpbmcgYSBwYXJ0aWN1bGFyIHF1YW50aXR5IG4gb2YgbWV0YWwgdG8gZm9yZ2UgYSBwYXJ0aWN1bGFyIHN3b3JkLCB0aGV5IGJlbGlldmVkIHRoYXQgc3dvcmQgd291bGQgYmUgbW9zdCBwb3dlcmZ1bCBpZiB0aGUgdGhpY2tuZXNzIGsgd2VyZSBjaG9zZW4gYWNjb3JkaW5nIHRvIHRoZSBmb2xsb3dpbmcgcnVsZTo8XC9wPlxyXG5cclxuPHA+R2l2ZW4gYSBub25uZWdhdGl2ZSBpbnRlZ2VyIG4sIHdoYXQgaXMgdGhlIHNtYWxsZXN0IGsgc3VjaCB0aGF0IHRoZSBkZWNpbWFsIHJlcHJlc2VudGF0aW9ucyBvZiB0aGUgaW50ZWdlcnMgaW4gdGhlIHNlcXVlbmNlOjxcL3A+XHJcblxyXG48cD5uLCAybiwgM24sIDRuLCA1biwgLi4uICwga248XC9wPlxyXG5cclxuPHA+Y29udGFpbiBhbGwgdGVuIGRpZ2l0cyAoMCB0aHJvdWdoIDkpIGF0IGxlYXN0IG9uY2U/PFwvcD5cclxuXHJcbjxwPkxvcmQgRWxyb25kIG9mIFJpdmVuZGVsbCBoYXMgY29tbWlzc2lvbmVkIHlvdSB3aXRoIHRoZSB0YXNrIHRvIGRldmVsb3AgYW4gYWxnb3JpdGhtIHRvIGZpbmQgdGhlIG9wdGltYWwgdGhpY2tuZXNzIChrKSBmb3IgYW55IGdpdmVuIHF1YW50aXR5IG9mIG1ldGFsIChuKS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPklucHV0IHdpbGwgY29uc2lzdCBvZiBhIHNpbmdsZSBpbnRlZ2VyIG4gcGVyIGxpbmUuIFRoZSBlbmQgb2YgaW5wdXQgd2lsbCBiZSBzaWduYWxlZCBieSBlbmQgb2YgbGUuIFRoZSBpbnB1dCBpbnRlZ2VyIHdpbGwgYmUgYmV0d2VlbiAxIGFuZCAyMDAsMDAwLDAwMCwgaW5jbHVzaXZlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBvdXRwdXQgd2lsbCBjb25zaXN0IG9mIGEgc2luZ2xlIGludGVnZXIgcGVyIGxpbmUsIGluZGljYXRpbmcgdGhlIHZhbHVlIG9mIGsgbmVlZGVkIHN1Y2ggdGhhdCBldmVyeSBkaWdpdCBmcm9tIDAgdGhyb3VnaCA5IGlzIHNlZW4gYXQgbGVhc3Qgb25jZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=