https://www.acwing.com/problem/content/description/4222/
ab%n=((a%n)b)%n
// a*b%n=((a%n)*b)%n
#include<iostream>
#include<queue>
using namespace std;
typedef pair<string,int> Node;
int n;
int main()
{
while(cin>>n,n)
{
queue<Node> q;
q.push({"1",1});
while(q.size()){
auto t=q.front();
q.pop();
if(t.second==0){
cout<<t.first<<endl;
break;
}
q.push({t.first+"0",t.second*10%n});
q.push({t.first+"1",(t.second*10+1)%n});
}
}
return 0;
}