시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 77 25 21 35.000%

문제

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

  • 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+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAxMDFcdWM3NDAgXHVhZDZjXHVjMGFjXHVhY2ZjXHVhYzAwIFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YjI5NCBcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc5MFx1YzVmMFx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIE5cdWM3NTggXHViYzMwXHVjMjE4XHVjNzc0XHViYTc0XHVjMTFjLCZuYnNwO1x1YWQ2Y1x1YzBhY1x1YWNmY1x1YWMwMCBcdWM4OGJcdWM1NDRcdWQ1NThcdWIyOTQgXHVjMjE4IFx1YzkxMVx1YzVkMFx1YzExYyBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YzIxOFx1Yjk3YyBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVChUICZsdDsgMTApXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBUXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM3OTBcdWM1ZjBcdWMyMTggTlx1Yzc3NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIE5cdWM3NDAgMSwwMDAsMDAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1YWMwMVx1YWMwMVx1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViOWM4XHViMmU0IE5cdWM3NTggXHViYzMwXHVjMjE4XHVjNzc0XHViYTc0XHVjMTFjLCBcdWFkNmNcdWMwYWNcdWFjZmNcdWFjMDAgXHVjODhiXHVjNTQ0XHVkNTU4XHViMjk0IFx1YzIxOCBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCZuYnNwO1x1YzIxOFx1Yjk3YyBcdWM1NDRcdWJiMzRcdWFjNzBcdWIwOTggXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM1N2QsIFx1YWRmOFx1YjdlY1x1ZDU1YyBcdWMyMThcdWFjMDAgXHVjNWM2XHViMmU0XHViYTc0Jm5ic3A7QlJBS1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiODExMiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6Ik9uZXMgQW5kIFplcm9zIDIiLCJkZXNjcmlwdGlvbiI6IjxwPkNlcnRhaW4gcG9zaXRpdmUgaW50ZWdlcnMgaGF2ZSB0aGVpciBkZWNpbWFsIHJlcHJlc2VudGF0aW9uIGNvbnNpc3Rpbmcgb25seSBvZiBvbmVzIGFuZCB6ZXJvcywgYW5kIGhhdmluZyBhdCBsZWFzdCBvbmUgZGlnaXQgb25lLCBlLmcuJm5ic3A7PGNvZGU+MTAxPFwvY29kZT4uIElmIGEgcG9zaXRpdmUgaW50ZWdlciBoYXMgbm90IHN1Y2ggYSBwcm9wZXJ0eSwgb25lIGNhbiB0cnkgdG8gbXVsdGlwbHkgaXQgYnkgc29tZSBwb3NpdGl2ZSBpbnRlZ2VyIHRvIGZpbmQgb3V0IHdoZXRoZXIgdGhlIHByb2R1Y3QgaGFzIHRoaXMgcHJvcGVydHkuPFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB3aGljaDo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5yZWFkcyBmcm9tIHRoZSBzdGFuZGFyZCBpbnB1dCBwb3NpdGl2ZSBpbnRlZ2VycyBuJm5ic3A7bm90IGdyZWF0ZXIgdGhhbiAxLDAwMCwwMDAsPFwvbGk+XHJcblx0PGxpPmZvciBlYWNoIGludGVnZXIgcmVhZCBjb21wdXRlcyB0aGUgY29ycmVjdCBhbnN3ZXIsPFwvbGk+XHJcblx0PGxpPndyaXRlcyB0aGUgYW5zd2VyIHRvIHRoZSBzdGFuZGFyZCBvdXRwdXQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+VGhlIGFuc3dlciBpcyBlaXRoZXIgdGhlIHNtYWxsZXN0IHBvc2l0aXZlIG11bHRpcGxlIG9mIG4mbmJzcDt3aG9zZSBkZWNpbWFsIHJlcHJlc2VudGF0aW9uIGNvbnNpc3RzIG9ubHkgb2YgemVyb3Mgb3Igb25lcywgb3IgdGhlIHdvcmQmbmJzcDs8Y29kZT5CUkFLPFwvY29kZT4mbmJzcDsoUG9saXNoIGZvciZuYnNwOzxlbT5hYnNlbmNlPFwvZW0+KSwgaWYgdGhlcmUgaXMgbm8gc3VjaCBtdWx0aXBsZS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBzdGFuZGFyZCBpbnB1dCBjb250YWlucyBpbiB0aGUgZmlyc3QgbGluZSBhIHBvc2l0aXZlIGludGVnZXIgSyAmbHQ7IDEwLiBJbiBjb25zZWN1dGl2ZSBsaW5lcyB0aGVyZSBpcyBhIHNlcXVlbmNlIG9mIEsmbmJzcDtudW1iZXJzIGluIHRoZSByYW5nZSBvZiBbMS4uLjEsMDAwLDAwMF0sIG9uZSBudW1iZXIgcGVyIGxpbmUuIFRoZSBudW1iZXJzIGluIHRoZSBzdGFuZGFyZCBpbnB1dCBhcmUgd3JpdHRlbiBjb3JyZWN0bHksIGFuZCB5b3VyIHByb2dyYW0gbmVlZCBub3QgdmVyaWZ5IHRoYXQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+RWFjaCBsaW5lIG9mIHRoZSBzdGFuZGFyZCBvdXRwdXQsIHN0YXJ0aW5nIHdpdGggdGhlIGZpcnN0LCBzaG91bGQgY29udGFpbjo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5laXRoZXIgb25seSBvbmUgd29yZCZuYnNwOzxjb2RlPkJSQUs8XC9jb2RlPiw8XC9saT5cclxuXHQ8bGk+b3IgZXhhY3RseSBvbmUgcG9zaXRpdmUgaW50ZWdlciBiZWluZyBhIG11bHRpcGxlIG9mIGEgc3VjY2Vzc2l2ZSBudW1iZXIgZ2l2ZW4gaW4gdGhlIGlucHV0OyBlYWNoIG11bHRpcGxlIG11c3QgYmUgYSBudW1iZXIgY29tcG9zZWQgb25seSBvZiBkaWdpdHMgMCZuYnNwO2FuZCAxLCBhbmQgaGFzIHRvIGJlIHdyaXR0ZW4gd2l0aCBubyBzcGFjZXMgYmV0d2VlbiB0aGUgZGlnaXRzLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPlRoZSBhbnN3ZXJzIGFyZSB0byBiZSB3cml0dGVuIGluIHN0YW5kYXJkIG91dHB1dCBpbiB0aGUgc2FtZSBvcmRlciBhcyB0aGUgY29ycmVzcG9uZGluZyBudW1iZXJzIGluIHN0YW5kYXJkIGlucHV0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==