시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 127 45 35 32.110%

문제

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

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

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

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

입력

첫째 줄에 테스트 케이스의 개수 T(T < 1,000)가 주어진다.

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

출력

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

예제 입력 1

6
17
11011
17
999
125
173

예제 출력 1

11101
11011
11101
111111111111111111111111111
1000
1011001101
W3sicHJvYmxlbV9pZCI6IjgxMTEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiIwXHVhY2ZjIDEiLCJkZXNjcmlwdGlvbiI6IjxwPlx1ZDNmNFx1Yjc4MFx1YjRkYyBcdWM2NTVcdWM3OTAgXHVhZDZjXHVjMGFjXHVhY2ZjXHViMjk0IFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVjMjE4XHViOTdjIFx1Yzg4Ylx1YzU0NFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4wXHVhY2ZjIDFcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuPFwvbGk+XHJcblx0PGxpPjFcdWM3NzQgXHVjODAxXHVjNWI0XHViM2M0IFx1ZDU1OFx1YjA5OCBcdWM3ODhcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL2xpPlxyXG5cdDxsaT5cdWMyMThcdWM3NTggXHVhZTM4XHVjNzc0XHVhYzAwIDEwMCBcdWM3NzRcdWQ1NThcdWM3NzRcdWIyZTQuPFwvbGk+XHJcblx0PGxpPlx1YzIxOFx1YWMwMCAwXHVjNzNjXHViODVjIFx1YzJkY1x1Yzc5MVx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+XHVjNjA4XHViOTdjIFx1YjRlNFx1YzViNCwgMTAxXHVjNzQwIFx1YWQ2Y1x1YzBhY1x1YWNmY1x1YWMwMCBcdWM4OGJcdWM1NDRcdWQ1NThcdWIyOTQgXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3OTBcdWM1ZjBcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBOXHVjNzU4IFx1YmMzMFx1YzIxOCBcdWM5MTFcdWM1ZDBcdWMxMWMgXHVhZDZjXHVjMGFjXHVhY2ZjXHVhYzAwIFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YjI5NCBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVhYzFjXHVjMjE4IFQoVCAmbHQ7IDEsMDAwKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgVFx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNzkwXHVjNWYwXHVjMjE4IE5cdWM3NzQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBOXHVjNzQwIDIwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCBOXHVjNzU4IFx1YmMzMFx1YzIxOFx1Yzc3NFx1YmE3NFx1YzExYywgXHVhZDZjXHVjMGFjXHVhY2ZjXHVhYzAwIFx1Yzg4Ylx1YzU0NFx1ZDU1OFx1YjI5NCBcdWMyMThcdWI5N2MgXHVjNTQ0XHViYjM0XHVhYzcwXHViMDk4IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHViOWNjXHVjNTdkLCBcdWFkZjhcdWI3ZWNcdWQ1NWMgXHVjMjE4XHVhYzAwIFx1YzVjNlx1YjJlNFx1YmE3NCZuYnNwO0JSQUtcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjgxMTEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJPbmVzIEFuZCBaZXJvcyIsImRlc2NyaXB0aW9uIjoiPHA+Q2VydGFpbiBwb3NpdGl2ZSBpbnRlZ2VycyBoYXZlIHRoZWlyIGRlY2ltYWwgcmVwcmVzZW50YXRpb24gY29uc2lzdGluZyBvbmx5IG9mIG9uZXMgYW5kIHplcm9zLCBhbmQgaGF2aW5nIGF0IGxlYXN0IG9uZSBkaWdpdCBvbmUsIGUuZy4mbmJzcDs8Y29kZT4xMDE8XC9jb2RlPi4gSWYgYSBwb3NpdGl2ZSBpbnRlZ2VyIGhhcyBub3Qgc3VjaCBhIHByb3BlcnR5LCBvbmUgY2FuIHRyeSB0byBtdWx0aXBseSBpdCBieSBzb21lIHBvc2l0aXZlIGludGVnZXIgdG8gZmluZCBvdXQgd2hldGhlciB0aGUgcHJvZHVjdCBoYXMgdGhpcyBwcm9wZXJ0eS48XC9wPlxyXG5cclxuPHA+V3JpdGUgYSBwcm9ncmFtIHdoaWNoOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPnJlYWRzIGZyb20gdGhlIHN0YW5kYXJkIGlucHV0IHBvc2l0aXZlIGludGVnZXJzIG4mbmJzcDtub3QgZ3JlYXRlciB0aGFuIDIwLDAwMCw8XC9saT5cclxuXHQ8bGk+Zm9yIGVhY2ggaW50ZWdlciByZWFkIGNvbXB1dGVzIGEgY29ycmVjdCBhbnN3ZXIsPFwvbGk+XHJcblx0PGxpPndyaXRlcyB0aGUgYW5zd2VyIHRvIHRoZSBzdGFuZGFyZCBvdXRwdXQuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+VGhlIGFuc3dlciBpcyBlaXRoZXIgYSBwb3NpdGl2ZSBtdWx0aXBsZSBvZiBuJm5ic3A7d2hvc2UgZGVjaW1hbCByZXByZXNlbnRhdGlvbiBjb25zaXN0cyBvZiBhdCBtb3N0IDEwMCAoYSBodW5kcmVkKSBkaWdpdHMsIG9ubHkgemVyb3Mgb3Igb25lcywgb3IgdGhlIHdvcmQmbmJzcDs8Y29kZT5CUkFLPFwvY29kZT4mbmJzcDsoJnF1b3Q7PGVtPmFic2VuY2U8XC9lbT4mcXVvdDspLCBpZiB0aGVyZSBpcyBubyBzdWNoIG11bHRpcGxlLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIHN0YW5kYXJkIGlucHV0IGNvbnRhaW5zIGluIHRoZSBmaXJzdCBsaW5lIGEgcG9zaXRpdmUgaW50ZWdlciBLICZsdDsgMSwwMDAuIEluIGNvbnNlY3V0aXZlIGxpbmVzIHRoZXJlIGlzIGEgc2VxdWVuY2Ugb2YgSyZuYnNwO251bWJlcnMgaW4gdGhlIHJhbmdlIG9mIFsxLi4uMjAsMDAwXSwgb25lIG51bWJlciBwZXIgbGluZS4gVGhlIG51bWJlcnMgaW4gdGhlIHN0YW5kYXJkIGlucHV0IGFyZSB3cml0dGVuIGNvcnJlY3RseSwgYW5kIHlvdXIgcHJvZ3JhbSBuZWVkIG5vdCB2ZXJpZnkgdGhhdC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5FYWNoIGxpbmUgb2YgdGhlIHN0YW5kYXJkIG91dHB1dCwgc3RhcnRpbmcgd2l0aCB0aGUgZmlyc3QsIHNob3VsZCBjb250YWluOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPmVpdGhlciBvbmx5IG9uZSB3b3JkJm5ic3A7PGNvZGU+QlJBSzxcL2NvZGU+LDxcL2xpPlxyXG5cdDxsaT5vciBleGFjdGx5IG9uZSBwb3NpdGl2ZSBpbnRlZ2VyIGJlaW5nIGEgbXVsdGlwbGUgb2YgYSBzdWNjZXNzaXZlIG51bWJlciBnaXZlbiBpbiB0aGUgaW5wdXQ7IGVhY2ggbXVsdGlwbGUgbXVzdCBiZSBhIG51bWJlciBjb21wb3NlZCBvbmx5IG9mIGRpZ2l0cyAwJm5ic3A7YW5kIDEsIGFuZCBoYXMgdG8gYmUgd3JpdHRlbiB3aXRoIG5vIHNwYWNlcyBiZXR3ZWVuIHRoZSBkaWdpdHMuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+VGhlIGFuc3dlcnMgYXJlIHRvIGJlIHdyaXR0ZW4gaW4gc3RhbmRhcmQgb3V0cHV0IGluIHRoZSBzYW1lIG9yZGVyIGFzIHRoZSBjb3JyZXNwb25kaW5nIG51bWJlcnMgaW4gc3RhbmRhcmQgaW5wdXQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d