#include<cstdio>

#include<stdio.h>

#include<cstdlib>

#include<cmath>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<vector>

#include<queue>

#define INF 0x3f3f3f3f

#define MAX 1005

using namespace std;

int n;

void BFS()

{

    queue<long long>Q;

    long long num;

    Q.push();

    while(!Q.empty())

    {

        num=Q.front();

        Q.pop();

        if(num%n==)

        {

            printf("%lld\n",num);

            return;

        }

        Q.push(num*);

        Q.push(num*+);

    }

}

int main()

{

    while(scanf("%d",&n),n)

    {

        BFS();

    }

    return ;

}