### Description

Given a positive integer n, write a program to find out a nonzero multiple m of n whose decimal representation contains only the digits 0 and 1. You may assume that n is not greater than 200 and there is a corresponding m containing no more than 100 decimal digits.

Input

The input file may contain multiple test cases. Each line contains a value of n (1 <= n <= 200). A line containing a zero terminates the input.

### Output

For each value of n in the input print a line containing the corresponding value of m. The decimal representation of m must not contain more than 100 digits. If there are multiple solutions for a given value of n, any one of them is acceptable.

### Sample Input

2 6 19 0

### Sample Output

10 100100100100100100 111111111111111111

Solution below . . .

/* * There are at least 3 ways to solve this: * * 1. NUMERICAL METHODS * * I found several links to numerical methods and couldn't * understand any of them. Here's a sample: * * https://bit.ly/2vSpGbc * * 2. CHEAT * * Input is guaranteed to be no more than 200, and results * have been computed for far more numbers than that * (see http://oeis.org/A004290/b004290.txt). * Put the answers in a hash table and just look them up. * * 3. BREADTH-FIRST SEARCH (BFS) * * Every node of the search tree will be a binary digit * number. For each number x, the next-level nodes will be * x0 and x1 (x concatenated with 0 and 1). * * We start by adding 1 to the queue, which will then * add 10 and 11 and so on. After taking a number from * the queue, we’ll check whether the number is a multiple * of the given number or not. If yes, we have our answer. * * Optimization: we're using a set for mod values. If a * number has a previously seen mod value, we don’t add * this new number to the queue. Explanation: Let * x and y be numbers that give the same value mod N. * Let x < y. Let z be another number which, when appended * to y gives a number divisible by N. Then we can also * append this number to x and get a number divisible by N. * So we can safely ignore y. * * NOTE: The sample outputs given for inputs 6 and 19 are * "acceptable" but much smaller answers are available. * */ import java.util.ArrayDeque; import java.util.Deque; import java.util.HashSet; import java.util.Scanner; import java.util.Set; public class Main { // returns smallest multiple which has // only 1s and 0s static long getMinimumMultiple(int N) { Deque<Long> q = new ArrayDeque<Long>(); Set<Long> visit = new HashSet<Long>(); long t = 1; // starting with 1 in queue q.add(t); // loop while queue is not empty while (!q.isEmpty()) { // Take the first number from queue. t = q.pop(); // Find remainder of t with respect to N. long rem = t % N; // if remainder is 0 then we have // found our solution if (rem == 0) return t; // If this remainder is not previously seen, // then add t + '0' and t + '1' to queue else if(!visit.contains(rem)) { visit.add(rem); q.add(t * 10); q.add(t * 10 + 1); } } return -1; //something went wrong } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); while (N != 0) { System.out.println(getMinimumMultiple(N)); N = sc.nextInt(); } sc.close(); } }