Description

At the 2008 Beijing Olympics, you want to become a torchbearer in Wenchuan, Sichuan. After multiple rounds of selection, you finally reach the last challenge.

This challenge is a hard problem: Given any positive integer $N$, find the smallest positive integer $M$ such that the decimal representation of $N \times M$ contains only 1 and 0.

Input Format

One line containing a positive integer $N$.

Output Format

Output one line. If a solution exists, output an integer representing the smallest $M$, otherwise output No Solution.

12

925

Hint

Constraints: $1 \le N \le 10^5$.

Translated by ChatGPT 5