提示: 欢迎访问OurACM平台。
Problem 1655 How many ones and zeros

Accept: 47    Submit: 260
Time Limit: 2000 mSec    Memory Limit : 32768 KB

Problem Description

Give you a positive integer N, you task is to find a minimum positive integer M such that the result of N * M only contains “1” and “0” and N * M > 1.

Input

There are multiple test cases. For each test case, there is an integer N(1<=N<=5000).

Output

For each test case, you should output the minimum positive integer M such that the result of N * M only contains “1” and “0”.

Sample Input

3

Sample Output

37

Source

FZU 2008 Summer Training III--Number Theory

Submit  Back  Status  Discuss