Torchbearer's Challenge

At the 2008 Beijing Olympics, you aspired to become a torchbearer from Sichuan, Wenchuan. After numerous rounds of selection, you have reached the final stage.

The challenge is as follows: Given a positive integer \(N\), find the smallest positive integer \(M\) such that the decimal representation of \(N \times M\) contains only the digits \(1\) and \(0\). In other words, you need to determine the minimal \(M\) for which \(N\times M\) is a number that is composed exclusively of 1's and 0's.

inputFormat

The input consists of a single positive integer \(N\).

outputFormat

Output the smallest positive integer \(M\) such that \(N\times M\) is made up solely of the digits 1 and 0.

sample

1

1