def dp(a,b,e):
    for i in range(1,b+1):
        g=a+9*(10**i)
        if g%e==0:
            return g
        ans=dp(g,i-1,e)
        if ans!=0:
            return ans    
    return 0

def solve(n):
    if n%2==0 or n%5==0:
        a=90
        b=0
        while True:
            if a%n==0:
                return str(a)
            ans=dp(a,b,n)
            if ans==0:
                a*=10
                b+=1
            else:
                return str(ans)
    else:
        a=90
        b=0
        if 9%n==0:
            return "9"
        while True:
            if (a+9)%n==0:
                return str(a+9)
            ans=dp(a+9,b,n)
            if ans==0:
                a*=10
                b+=1
            else:
                return str(ans)

string solve(int n) {
     int i = 1;

    while (true) {
        // Convert i to binary string
        string binary = "";
        int temp = i;
        while (temp > 0) {
            binary = (temp % 2 == 0 ? '0' : '9') + binary;
            temp /= 2;
        }

        // Convert to integer and check divisibility
        long long candidate = stoll(binary);
        if (candidate % n == 0) {
            return binary;
        }

        i++;
    }
    
    return "";

}

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);
}