string solve(int n) {
    long long res;
    queue<long long> q;
    set<long long> visited;
    q.push(9);
    while(!q.empty()){
        long long curr=q.front();
        if(curr%n==0){
            res=curr;
            break;
        }
        long long num1=curr*10;
        long long num2=curr*10+9;
        if(visited.find(num1)==visited.end()){
            q.push(num1);
            visited.insert(num1);
        }
        if(visited.find(num2)==visited.end()){
            q.push(num2);
            visited.insert(num2);
        }
        q.pop();
    }
    return to_string(res);
}