Smallest Multiplier Producing a 0-1 Product

Given an integer \(A\), find the smallest positive integer \(B\) such that the product \(A \times B\) contains only the digits 0 and 1 in its decimal representation.

In other words, let \(Y = A \times B\). You must choose the smallest possible \(B\) so that every digit of \(Y\) is either 0 or 1. It is guaranteed that such a \(B\) exists.

Hint: One way to approach the problem is to search for the smallest number \(Y\) which consists solely of 0s and 1s and is a multiple of \(A\). Then, \(B\) can be computed as \(Y \div A\).

inputFormat

The input consists of a single integer \(A\) on one line.

outputFormat

Output the smallest integer \(B\) such that every digit of \(A \times B\) is either 0 or 1.

sample

1

1