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.

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.

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.

2

6

19

0

10

100100100100100100

111111111111111111

#include<iostream>

#include<bits/stdc++.h>

#include<queue>

using namespace std;

void BFS(int x){

    queue<int> q ;

    q.push(1);

    int y;

    while (!q.empty())

    {

        y=q.front();

        q.pop();

        for (int i = 0; i < 2; i++)

        {

            if (i==0) q.push(y*10);

            else

                q.push(y*10+1);

            if (y%x==0)

            {

                cout<<y<<endl;

                return ;

            }

        }

    }

}

int main(){

    int x;

    while ((cin>>x)&&x)

    {

       BFS(x);

    }

}