Finding a Multiple Made Only of 0s and 1s

Given a positive integer n, find a non-zero multiple m of n whose decimal representation contains only the digits 0 and 1. The result must have no more than 100 digits.

Input

The input contains multiple test cases. Each line contains one positive integer n.

A line containing 0 marks the end of the input.

Output

For every value of n, print one valid multiple m on its own line. If several answers exist, any one of them is acceptable.

Constraints

1 ≤ n ≤ 200
The output contains only 0 and 1
The output is a non-zero multiple of n
The total number of digits does not exceed 100

Example

Input:

Output:

10
100100100100100100
111111111111111111

Approach

A direct search over increasingly large integers is impractical, because the required number may contain many digits. The useful observation is that when a number is extended by appending a digit, its remainder can be updated without constructing or storing the entire value:

new remainder = (old remainder × 10 + digit) % n

For example, appending 1 to a number with remainder r produces a new remainder of (r × 10 + 1) % n. Appending 0 produces (r × 10) % n. This is the same idea illustrated by:

11 % 2 = ((1 × 10) % 2 + 1) % 2

The search starts with the number 1. Each candidate is expanded in two ways: append 0, or append 1. A breadth-first search processes candidates in increasing order of length, while the queue stores both the constructed string and its remainder modulo n.

Whenever a candidate has remainder 0, it is a valid answer and can be printed immediately. Since only remainders from 0 through n - 1 are relevant, the search can be performed using modular values instead of large integer arithmetic. The implementation below follows this process and resets the queue before handling each test case.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;

queue<pair<string,ll>> ans;  //存储答案

int main()
{
    while(cin>>n&&n){

        while(ans.size()) ans.pop();  //清空数据

        ans.push({"1",1});  //将1入队，作为队头扩展搜索

        while(!ans.empty()){
            auto p=ans.front();
            ans.pop();
            if(p.second==0){  //满足条件输出，
                cout<<p.first<<endl;
                break;
            }
            ans.push({p.first+"0",(p.second*10)%n});  //末尾补零入队，并对其取模
            ans.push({p.first+"1",(p.second*10+1)%n});  //末尾补1入队，并对其取模
        }

    }

    return 0;
}