void bfs(int src , mod){
    memset(dis , -1 , sizeof dis);
    queue < int > que(src);
    dis[src] = 0;
    par[src] = -1;
    while(!que.empty()){
        int a = que.front();
        que.pop();
        for(int i = 0 ; i < 10 ; i++){
            int b = (a * 10 + i) % mod;
            if(dis[b] != -1){
                dis[b] = dis[a] + 1;
                que.push(b);
                par[b] = a;
                digit[b] = i;
            }
        }
    }
}



int main()
{
    /// problem: https://www.spoj.com/problems/MULTII/en/

    int ans = MAX; /// min number of digits
    for(int dig = 1 ; dig < 10 ; dig++){
        if(valid[dig]){
            bfs(dig % N , N);
            if(dis[0] != -1) ans = min(ans , dis[0]);
        }
    }

    for(int dig = 1 ; dig < 10 ; dig++){
        if(valid[dig]){
            bfs(dig % N , N);
            if(dis[0] == ans){
                string num;
                int cur = 0;
                int src = dig % N;
                while(cur != src){
                    num += digit[cur] + '0';
                    cur = par[cur];
                }
                num += dig + '0';
                reverse(num.begin() , num.end());
                cout<<num<<endl;
                return 0;
            }
        }
    }

}