poj1426 BFS 王道P144 todoTime Limit Exceeded

//poj1426   BFS 王道P144
//http://poj.org/submit?problem_id=1426
//Time Limit Exceeded
#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

//
//long long BFS(int n){
//  queue<long long> myQueue;
//  myQueue.push(1);
//  while(!myQueue.empty()){
//      long long current = myQueue.front();
//      myQueue.pop();
//      if(current % n == 0){
//          return current;
//      }
//      myQueue.push(current * 10);
//      myQueue.push(current * 10 +1);
//  }
//
//}


void BFS(int n){
    queue<long long> myQueue;
    myQueue.push(1);
    while(!myQueue.empty()){
        long long current = myQueue.front();
        myQueue.pop();
        if(current % n == 0){
            printf("%lld\n",current);
            return ;
        }
        myQueue.push(current * 10);
        myQueue.push(current * 10 +1);
    }

}

int main(){
    int n;
    while(scanf("%d",&n) != EOF){
        if(n==0) break;
//        printf("%lld\n",BFS(n));
        BFS(n);
    }

    return 0;
}