시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 256 MB125340730031.881%

문제

폴란드 왕자 구사과는 다음과 같은 수를 좋아한다.

  • 0과 1로만 이루어져 있어야 한다.
  • 1이 적어도 하나 있어야 한다.
  • 수가 0으로 시작하지 않는다.

예를 들어, 101은 구사과가 좋아하는 수이다.

자연수 N이 주어졌을 때, N의 배수이면서, 구사과가 좋아하는 수 중에서 가장 작은 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T(T ≤ 10)가 주어진다.

둘째 줄부터 T개의 줄에는 자연수 N이 한 줄에 하나씩 주어진다. N은 1,000,000보다 작거나 같은 자연수이다.

출력

각각의 테스트 케이스마다 N의 배수이면서, 구사과가 좋아하는 수 중에서 가장 작은 수를 출력한다. 만약, 그러한 수가 없다면 BRAK을 출력한다.

예제 입력 1

6
17
11011
17
999
125
173

예제 출력 1

11101
11011
11101
111111111111111111111111111
1000
1011001101
W3sicHJvYmxlbV9pZCI6IjgxMTIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiIwXHVhY2ZjIDEgLSAyIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQzZjRcdWI3ODBcdWI0ZGMgXHVjNjU1XHVjNzkwIFx1YWQ2Y1x1YzBhY1x1YWNmY1x1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YzIxOFx1Yjk3YyBcdWM4OGJcdWM1NDRcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+MFx1YWNmYyAxXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT4xXHVjNzc0IFx1YzgwMVx1YzViNFx1YjNjNCBcdWQ1NThcdWIwOTggXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9saT5cclxuXHQ8bGk+XHVjMjE4XHVhYzAwIDBcdWM3M2NcdWI4NWMgXHVjMmRjXHVjNzkxXHVkNTU4XHVjOWMwIFx1YzU0YVx1YjI5NFx1YjJlNC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAxMDFcdWM3NDAgXHVhZDZjXHVjMGFjXHVhY2ZjXHVhYzAwIFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YjI5NCBcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc5MFx1YzVmMFx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIE5cdWM3NTggXHViYzMwXHVjMjE4XHVjNzc0XHViYTc0XHVjMTFjLCZuYnNwO1x1YWQ2Y1x1YzBhY1x1YWNmY1x1YWMwMCBcdWM4OGJcdWM1NDRcdWQ1NThcdWIyOTQgXHVjMjE4IFx1YzkxMVx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVChUICZsZTsgMTApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBUXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM3OTBcdWM1ZjBcdWMyMTggTlx1Yzc3NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIE5cdWM3NDAgMSwwMDAsMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IE5cdWM3NTggXHViYzMwXHVjMjE4XHVjNzc0XHViYTc0XHVjMTFjLCBcdWFkNmNcdWMwYWNcdWFjZmNcdWFjMDAgXHVjODhiXHVjNTQ0XHVkNTU4XHViMjk0IFx1YzIxOCBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCZuYnNwO1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YjljY1x1YzU3ZCwgXHVhZGY4XHViN2VjXHVkNTVjIFx1YzIxOFx1YWMwMCBcdWM1YzZcdWIyZTRcdWJhNzQmbmJzcDtCUkFLXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI4MTEyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiT25lcyBBbmQgWmVyb3MgMiIsImRlc2NyaXB0aW9uIjoiPHA+Q2VydGFpbiBwb3NpdGl2ZSBpbnRlZ2VycyBoYXZlIHRoZWlyIGRlY2ltYWwgcmVwcmVzZW50YXRpb24gY29uc2lzdGluZyBvbmx5IG9mIG9uZXMgYW5kIHplcm9zLCBhbmQgaGF2aW5nIGF0IGxlYXN0IG9uZSBkaWdpdCBvbmUsIGUuZy4mbmJzcDs8Y29kZT4xMDE8XC9jb2RlPi4gSWYgYSBwb3NpdGl2ZSBpbnRlZ2VyIGhhcyBub3Qgc3VjaCBhIHByb3BlcnR5LCBvbmUgY2FuIHRyeSB0byBtdWx0aXBseSBpdCBieSBzb21lIHBvc2l0aXZlIGludGVnZXIgdG8gZmluZCBvdXQgd2hldGhlciB0aGUgcHJvZHVjdCBoYXMgdGhpcyBwcm9wZXJ0eS48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHdoaWNoOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnJlYWRzIGZyb20gdGhlIHN0YW5kYXJkIGlucHV0IHBvc2l0aXZlIGludGVnZXJzIG4mbmJzcDtub3QgZ3JlYXRlciB0aGFuIDEsMDAwLDAwMCw8XC9saT5cclxuXHQ8bGk+Zm9yIGVhY2ggaW50ZWdlciByZWFkIGNvbXB1dGVzIHRoZSBjb3JyZWN0IGFuc3dlciw8XC9saT5cclxuXHQ8bGk+d3JpdGVzIHRoZSBhbnN3ZXIgdG8gdGhlIHN0YW5kYXJkIG91dHB1dC48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5UaGUgYW5zd2VyIGlzIGVpdGhlciB0aGUgc21hbGxlc3QgcG9zaXRpdmUgbXVsdGlwbGUgb2YgbiZuYnNwO3dob3NlIGRlY2ltYWwgcmVwcmVzZW50YXRpb24gY29uc2lzdHMgb25seSBvZiB6ZXJvcyBvciBvbmVzLCBvciB0aGUgd29yZCZuYnNwOzxjb2RlPkJSQUs8XC9jb2RlPiZuYnNwOyhQb2xpc2ggZm9yJm5ic3A7PGVtPmFic2VuY2U8XC9lbT4pLCBpZiB0aGVyZSBpcyBubyBzdWNoIG11bHRpcGxlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIHN0YW5kYXJkIGlucHV0IGNvbnRhaW5zIGluIHRoZSBmaXJzdCBsaW5lIGEgcG9zaXRpdmUgaW50ZWdlciBLICZsZTsgMTAuIEluIGNvbnNlY3V0aXZlIGxpbmVzIHRoZXJlIGlzIGEgc2VxdWVuY2Ugb2YgSyZuYnNwO251bWJlcnMgaW4gdGhlIHJhbmdlIG9mIFsxLi4uMSwwMDAsMDAwXSwgb25lIG51bWJlciBwZXIgbGluZS4gVGhlIG51bWJlcnMgaW4gdGhlIHN0YW5kYXJkIGlucHV0IGFyZSB3cml0dGVuIGNvcnJlY3RseSwgYW5kIHlvdXIgcHJvZ3JhbSBuZWVkIG5vdCB2ZXJpZnkgdGhhdC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5FYWNoIGxpbmUgb2YgdGhlIHN0YW5kYXJkIG91dHB1dCwgc3RhcnRpbmcgd2l0aCB0aGUgZmlyc3QsIHNob3VsZCBjb250YWluOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPmVpdGhlciBvbmx5IG9uZSB3b3JkJm5ic3A7PGNvZGU+QlJBSzxcL2NvZGU+LDxcL2xpPlxyXG5cdDxsaT5vciBleGFjdGx5IG9uZSBwb3NpdGl2ZSBpbnRlZ2VyIGJlaW5nIGEgbXVsdGlwbGUgb2YgYSBzdWNjZXNzaXZlIG51bWJlciBnaXZlbiBpbiB0aGUgaW5wdXQ7IGVhY2ggbXVsdGlwbGUgbXVzdCBiZSBhIG51bWJlciBjb21wb3NlZCBvbmx5IG9mIGRpZ2l0cyAwJm5ic3A7YW5kIDEsIGFuZCBoYXMgdG8gYmUgd3JpdHRlbiB3aXRoIG5vIHNwYWNlcyBiZXR3ZWVuIHRoZSBkaWdpdHMuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+VGhlIGFuc3dlcnMgYXJlIHRvIGJlIHdyaXR0ZW4gaW4gc3RhbmRhcmQgb3V0cHV0IGluIHRoZSBzYW1lIG9yZGVyIGFzIHRoZSBjb3JyZXNwb25kaW5nIG51bWJlcnMgaW4gc3RhbmRhcmQgaW5wdXQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > Polish Olympiad in Informatics > POI 1994/1995 > Stage 1 3번