시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 107 48 45 49.451%

문제

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

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

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

이 때, 0~9까지 모든 숫자를 포함하는 가장 작은 k를 찾아야 한다.

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

입력

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

출력

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

예제 입력

1
10
123456789
3141592

예제 출력

10
9
3
5

힌트