시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 256 MB 69 28 14 53.846%

문제

철수는 혼자서 자연수 게임을 하고 있다. 자연수 게임을 하려면 파란 종이 한 장과 빨간 종이 한 장이 필요하다. 가장 처음에 두 종이에는 모두 1이 적혀있다.

게임은 두 종이 적힌 수의 합을 구하고, 그 값을 하나의 종이에 바꿔 적는 방식으로 진행된다. 이 과정 한 번을 "덧셈"이라고 부른다. "덧셈"을 반복해서 두 종이 중 하나에 철수가 원하는 수 x가 적히면 게임이 종료된다.

1보다 큰 정수 x에 대해서 게임을 할 때 계속 같은 색의 종이만 고른다면, 항상 x-1번의 덧셈 후에 게임이 끝난다. 철수는 x를 만드는 덧셈의 최소 횟수가 궁금해졌다. x가 주어졌을 때, 게임이 종료되는 덧셈의 최소 횟수를 구해보자.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 둘째 줄부터 T개의 줄에 x가 한 줄에 하나씩 주어진다.

출력

각각의 테스트 케이스마다 x를 만들기 위한 방법 중 덧셈 횟수가 최소인 것을 한 줄에 하나씩 출력한다.

x를 만드는 최소 덧셈 횟수가 M번인 경우에는 길이가 M인 문자열을 출력해야 하고, 파란 종이를 고른 것은 B, 빨간 종이를 고른 것은 R이다. 최소 덧셈 횟수를 만드는 방법이 여러가지인 경우에는 아무거나 출력한다.

제한

  • 1 ≤ T ≤ 100
  • 모든 테스트케이스의 x의 합은 20,000,000 이하이다.

서브태스크 1 (10점)

  • 1 ≤ x ≤ 500

서브태스크 2 (22점)

  • 1 ≤ x ≤ 300,000

예제 입력 1

4
2
3
4
5

예제 출력 1

B
RB
RRR
RBR

힌트

x = 5인 경우 아래와 같이 다양한 방법으로 5를 만들 수 있다. B는 파란 종이, R은 빨간 종이를 의미하고, 알파벳의 뒤에 적힌 수는 해당 종이에 적힌 수이다.

  • (B1, R1) → B를 선택 → (B2, R1) → R을 선택 → (B2, R3) → B를 선택 → (B5, R3) → 종료 (덧셈 3번)
  • (B1, R1) → B를 선택 → (B2, R1) → B를 선택 → (B3, R1) → B를 선택 → (B4, R1) → B를 선택 → (B5, R1) → 종료 (덧셈 4번)
W3sicHJvYmxlbV9pZCI6IjE3NDMxIiwicHJvYmxlbV9sYW5nIjoiMCIsInRpdGxlIjoiXHVhYzhjXHVjNzg0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWNjYTBcdWMyMThcdWIyOTQgXHVkNjNjXHVjNzkwXHVjMTFjIFx1Yzc5MFx1YzVmMFx1YzIxOCBcdWFjOGNcdWM3ODRcdWM3NDQgXHVkNTU4XHVhY2UwIFx1Yzc4OFx1YjJlNC4gXHVjNzkwXHVjNWYwXHVjMjE4IFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NThcdWI4MjRcdWJhNzQgXHVkMzBjXHViNzgwIFx1Yzg4NVx1Yzc3NCBcdWQ1NWMgXHVjN2E1XHVhY2ZjIFx1YmU2OFx1YWMwNCBcdWM4ODVcdWM3NzQgXHVkNTVjIFx1YzdhNVx1Yzc3NCBcdWQ1NDRcdWM2OTRcdWQ1NThcdWIyZTQuIFx1YWMwMFx1YzdhNSBcdWNjOThcdWM3NGNcdWM1ZDAmbmJzcDtcdWI0NTAgXHVjODg1XHVjNzc0XHVjNWQwXHViMjk0IFx1YmFhOFx1YjQ1MCAxXHVjNzc0IFx1YzgwMVx1ZDYwMFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzhjXHVjNzg0XHVjNzQwIFx1YjQ1MCBcdWM4ODVcdWM3NzQgXHVjODAxXHVkNzhjIFx1YzIxOFx1Yzc1OCBcdWQ1NjlcdWM3NDQgXHVhZDZjXHVkNTU4XHVhY2UwLCBcdWFkZjggXHVhYzEyXHVjNzQ0IFx1ZDU1OFx1YjA5OFx1Yzc1OCBcdWM4ODVcdWM3NzRcdWM1ZDAgXHViYzE0XHVhZmQ0IFx1YzgwMVx1YjI5NCBcdWJjMjlcdWMyZGRcdWM3M2NcdWI4NWMgXHVjOWM0XHVkNTg5XHViNDFjXHViMmU0LiBcdWM3NzQgXHVhY2ZjXHVjODE1IFx1ZDU1YyBcdWJjODhcdWM3NDQgJnF1b3Q7XHViMzY3XHVjMTQ4JnF1b3Q7XHVjNzc0XHViNzdjXHVhY2UwIFx1YmQ4MFx1Yjk3OFx1YjJlNC4gJnF1b3Q7XHViMzY3XHVjMTQ4JnF1b3Q7XHVjNzQ0IFx1YmMxOFx1YmNmNVx1ZDU3NFx1YzExYyBcdWI0NTAgXHVjODg1XHVjNzc0IFx1YzkxMSBcdWQ1NThcdWIwOThcdWM1ZDAgXHVjY2EwXHVjMjE4XHVhYzAwIFx1YzZkMFx1ZDU1OFx1YjI5NCBcdWMyMTggeFx1YWMwMCBcdWM4MDFcdWQ3ODhcdWJhNzQgXHVhYzhjXHVjNzg0XHVjNzc0IFx1Yzg4NVx1YjhjY1x1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+MVx1YmNmNFx1YjJlNCBcdWQwNzAgXHVjODE1XHVjMjE4IHhcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWQ1NjAgXHViNTRjIFx1YWNjNFx1YzE4ZCBcdWFjMTlcdWM3NDAgXHVjMGM5XHVjNzU4IFx1Yzg4NVx1Yzc3NFx1YjljYyBcdWFjZTBcdWI5NzhcdWIyZTRcdWJhNzQsIFx1ZDU2ZFx1YzBjMSB4LTFcdWJjODhcdWM3NTggXHViMzY3XHVjMTQ4IFx1ZDZjNFx1YzVkMCBcdWFjOGNcdWM3ODRcdWM3NzQgXHViMDVkXHViMDljXHViMmU0LiBcdWNjYTBcdWMyMThcdWIyOTQgeFx1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHViMzY3XHVjMTQ4XHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWQ2OWZcdWMyMThcdWFjMDAgXHVhZDgxXHVhZTA4XHVkNTc0XHVjODRjXHViMmU0LiB4XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWM4Y1x1Yzc4NFx1Yzc3NCBcdWM4ODVcdWI4Y2NcdWI0MThcdWIyOTQgXHViMzY3XHVjMTQ4XHVjNzU4IFx1Y2Q1Y1x1YzE4YyBcdWQ2OWZcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOCBUXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBUXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCB4XHVhYzAwIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDFcdWFjMDFcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjljOFx1YjJlNCB4XHViOTdjIFx1YjljY1x1YjRlNFx1YWUzMCBcdWM3MDRcdWQ1NWMgXHViYzI5XHViYzk1IFx1YzkxMSBcdWIzNjdcdWMxNDggXHVkNjlmXHVjMjE4XHVhYzAwIFx1Y2Q1Y1x1YzE4Y1x1Yzc3OCBcdWFjODNcdWM3NDQgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD54XHViOTdjIFx1YjljY1x1YjRkY1x1YjI5NCBcdWNkNWNcdWMxOGMgXHViMzY3XHVjMTQ4IFx1ZDY5Zlx1YzIxOFx1YWMwMCBNXHViYzg4XHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWFlMzhcdWM3NzRcdWFjMDAgTVx1Yzc3OCBcdWJiMzhcdWM3OTBcdWM1ZjRcdWM3NDQgXHVjZDljXHViODI1XHVkNTc0XHVjNTdjIFx1ZDU1OFx1YWNlMCwgXHVkMzBjXHViNzgwIFx1Yzg4NVx1Yzc3NFx1Yjk3YyBcdWFjZTBcdWI5NzggXHVhYzgzXHVjNzQwIEIsIFx1YmU2OFx1YWMwNCBcdWM4ODVcdWM3NzRcdWI5N2MgXHVhY2UwXHViOTc4IFx1YWM4M1x1Yzc0MCBSXHVjNzc0XHViMmU0LiBcdWNkNWNcdWMxOGMgXHViMzY3XHVjMTQ4IFx1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHViYzI5XHViYzk1XHVjNzc0IFx1YzVlY1x1YjdlY1x1YWMwMFx1YzljMFx1Yzc3OCBcdWFjYmRcdWM2YjBcdWM1ZDBcdWIyOTQgXHVjNTQ0XHViYjM0XHVhYzcwXHViMDk4IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiPHA+eCA9IDVcdWM3NzggXHVhY2JkXHVjNmIwIFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NzQgXHViMmU0XHVjNTkxXHVkNTVjIFx1YmMyOVx1YmM5NVx1YzczY1x1Yjg1YyA1XHViOTdjIFx1YjljY1x1YjRlNCBcdWMyMTggXHVjNzg4XHViMmU0LiBCXHViMjk0IFx1ZDMwY1x1Yjc4MCBcdWM4ODVcdWM3NzQsIFJcdWM3NDAgXHViZTY4XHVhYzA0IFx1Yzg4NVx1Yzc3NFx1Yjk3YyBcdWM3NThcdWJiZjhcdWQ1NThcdWFjZTAsIFx1YzU0Y1x1ZDMwY1x1YmNiM1x1Yzc1OCBcdWI0YTRcdWM1ZDAgXHVjODAxXHVkNzhjIFx1YzIxOFx1YjI5NCBcdWQ1NzRcdWIyZjkgXHVjODg1XHVjNzc0XHVjNWQwIFx1YzgwMVx1ZDc4YyBcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+KEIxLCBSMSkmbmJzcDsmcmFycjsgQlx1Yjk3YyBcdWMxMjBcdWQwZGQmbmJzcDsmcmFycjsgKEIyLCBSMSkmbmJzcDsmcmFycjsgUlx1Yzc0NCBcdWMxMjBcdWQwZGQmbmJzcDsmcmFycjsgKEIyLCBSMykmbmJzcDsmcmFycjsgQlx1Yjk3YyBcdWMxMjBcdWQwZGQmbmJzcDsmcmFycjsgKEI1LCBSMykmbmJzcDsmcmFycjsgXHVjODg1XHViOGNjIChcdWIzNjdcdWMxNDggM1x1YmM4OCk8XC9saT5cclxuXHQ8bGk+KEIxLCBSMSkmbmJzcDsmcmFycjsgQlx1Yjk3YyBcdWMxMjBcdWQwZGQmbmJzcDsmcmFycjsgKEIyLCBSMSkmbmJzcDsmcmFycjsgQlx1Yjk3YyBcdWMxMjBcdWQwZGQmbmJzcDsmcmFycjsgKEIzLCBSMSkmbmJzcDsmcmFycjsgQlx1Yjk3YyBcdWMxMjBcdWQwZGQmbmJzcDsmcmFycjsgKEI0LCBSMSkmbmJzcDsmcmFycjsgQlx1Yjk3YyBcdWMxMjBcdWQwZGQgJnJhcnI7IChCNSwgUjEpICZyYXJyOyBcdWM4ODVcdWI4Y2MgKFx1YjM2N1x1YzE0OCA0XHViYzg4KTxcL2xpPlxyXG48XC91bD5cclxuIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQiLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+MSAmbGU7IFQgJmxlOyAxMDA8XC9saT5cclxuXHQ8bGk+XHViYWE4XHViNGUwIFx1ZDE0Y1x1YzJhNFx1ZDJiOFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCB4XHVjNzU4IFx1ZDU2OVx1Yzc0MCZuYnNwOzIwLDAwMCwwMDAgXHVjNzc0XHVkNTU4XHVjNzc0XHViMmU0LjxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8dWw+XHJcblx0PGxpPjEgJmxlOyB4ICZsZTsgNTAwPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMiI6Ijx1bD5cclxuXHQ8bGk+MSAmbGU7IHggJmxlOyAzMDAsMDAwPFwvbGk+XHJcbjxcL3VsPlxyXG4ifSx7InByb2JsZW1faWQiOiIxNzQzMSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkdhbWUiLCJkZXNjcmlwdGlvbiI6IjxwPkFsYmVydCBpcyBwbGF5aW5nIGEgZ2FtZSB3aXRoIG51bWJlcnMuIFRvIHBsYXkgdGhlIGdhbWUsIGhlIG5lZWRzIHR3byBzaGVldHMmbmJzcDtvZiBwYXBlciwgb25lIGluIGJsdWUgYW5kIGFub3RoZXIgaW4gcmVkLiBBdCBmaXJzdCwgYm90aCBzaGVldHMgaGF2ZSBudW1iZXIgJnF1b3Q7MSZxdW90OyB3cml0dGVuIG9uIHRoZW0uPFwvcD5cclxuXHJcbjxwPkFsYmVydCBwbGF5cyB0aGUgZ2FtZSBhcyBmb2xsb3dzLiBGaXJzdCBoZSBjYWxjdWxhdGVzIHRoZSBzdW0gb2YgdGhlIHR3byBudW1iZXJzIHdyaXR0ZW4gb24gdGhlIHNoZWV0cy4gSGUgdGhlbiByZXBsYWNlcyB0aGUgbnVtYmVyIG9uIG9uZSBvZiB0aGUgc2hlZXRzIGJ5IHRoaXMgc3VtLiBPbmUgc3VjaCBtb3ZlIGlzIGNhbGxlZCBhbiAmcXVvdDthZGRpdGlvbiZxdW90Oy4gQWZ0ZXIgYXBwbHlpbmcgYWRkaXRpb24ocyksIEFsYmVydCBlbmRzIHRoZSBnYW1lIHdoZW4gb25lIG9mIHRoZSBzaGVldHMgaGFzIHggd3JpdHRlbiBvbiBpdCAodGhlIG51bWJlciBoZSBpbml0aWFsbHkgY2hvb3NlcyB0byBwbGF5IHRoaXMgZ2FtZSkuPFwvcD5cclxuXHJcbjxwPkZvciBldmVyeSBpbnRlZ2VyIHggJmd0OyAxLCBpZiBBbGJlcnQgY2hvb3NlcyB0byB3cml0ZSBvbmx5IG9uIHRoZSBzYW1lIGNvbG9yIHNoZWV0LCB0aGVuIGFmdGVyICh4LTEpIGFkZGl0aW9ucyB0aGUgZ2FtZSBhbHdheXMgZW5kcy4gQWxiZXJ0IHdhbnRzIHRvIGtub3cgdGhlIG1pbmltdW0gbnVtYmVyIG9mIGFkZGl0aW9ucyBoZSBuZWVkcyB0byBwZXJmb3JtIGluIG9yZGVyIHRvIHJlYWNoIHguPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSB3aWxsIGNvbnRhaW4gVCwgdGhlIG51bWJlciBvZiB0ZXN0IGNhc2VzLjxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBuZXh0IFQgbGluZXMgd2lsbCBjb250YWluIGEgc2luZ2xlIGludGVnZXIgeC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB0ZXN0IGNhc2UsIHlvdSBtdXN0IG91dHB1dCBhIHN0cmluZyB0aGF0IGRlc2NyaWJlcyBob3cgQWxiZXJ0IGNhbiByZWFjaCB4IHdpdGggbWluaW11bSBudW1iZXIgb2YgYWRkaXRpb25zLjxcL3A+XHJcblxyXG48cD5JZiBNIGlzIHRoZSBtaW5pbXVtIG51bWJlciBvZiBhZGRpdGlvbnMgQWxiZXJ0IG11c3QgZG8gaW4gb3JkZXIgdG8gZ2V0IHgsIHRoZW4gdGhlIG91dHB1dCBtdXN0IGJlIGEgc3RyaW5nIG9mIGxlbmd0aCBNLiBFYWNoIGNoYXJhY3RlciBzaG91bGQgYmUgZWl0aGVyIEIgb3IgUiBkZXBlbmRpbmcgb24gd2hpY2ggY29sb3JlZCBzaGVldCBBbGJlcnQgbXVzdCB3cml0ZSB0aGUgc3VtbWVkIG51bWJlciBvbi4gSWYgdGhlcmUgYXJlIG11bHRpcGxlIHdheXMgdG8gYWNoaWV2ZSB0aGUgbWluaW11bSBudW1iZXIgb2YgYWRkaXRpb25zLCB5b3UgbWF5IG91dHB1dCBhbnkgb25lIG9mIHRoZW0uPFwvcD5cclxuIiwiaGludCI6IjxwPldoZW4geCA9IDUsIHRoZXJlIGFyZSBtYW55IHdheXMgdG8gcmVhY2ggNS48XC9wPlxyXG5cclxuPHA+QiByZXByZXNlbnRzIGJsdWUgc2hlZXQgYW5kIFIgcmVwcmVzZW50cyByZWQgc2hlZXQuIFRoZSBudW1iZXIgYWZ0ZXIgQiBvciBSIHJlcHJlc2VudHMgdGhlIG51bWJlciB3cml0dGVuIG9uIHRoZSByZXNwZWN0aXZlIHNoZWV0LjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPihCMSwgUjEpIC0mZ3Q7IEFsYmVydCBjaG9vc2VzIEIgLSZndDsgKEIyLCBSMSkgLSZndDsgQWxiZXJ0IGNob29zZXMgUiAtJmd0OyAoQjIsIFIzKSAtJmd0OyBBbGJlcnQgY2hvb3NlcyBCIC0mZ3Q7IChCNSwgUjMpIC0mZ3Q7IEdhbWUgZW5kcyAoMyBhZGRpdGlvbnMpLjxcL2xpPlxyXG5cdDxsaT4oQjEsIFIxKSAtJmd0OyBBbGJlcnQgY2hvb3NlcyBCIC0mZ3Q7IChCMiwgUjEpIC0mZ3Q7IEFsYmVydCBjaG9vc2VzIEIgLSZndDsgKEIzLCBSMSkgLSZndDsgQWxiZXJ0IGNob29zZXMgQiAtJmd0OyAoQjQsIFIxKSAtJmd0OyBBbGJlcnQgY2hvb3NlcyBCIC0mZ3Q7IChCNSwgUjEpIC0mZ3Q7IEdhbWUgZW5kcyAoNCBhZGRpdGlvbnMpLjxcL2xpPlxyXG48XC91bD5cclxuIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQiLCJsaW1pdCI6Ijx1bD5cclxuXHQ8bGk+MSAmbGU7IFQgJmxlOyAxMDA8XC9saT5cclxuXHQ8bGk+VGhlIHN1bSBvZiBhbGwgeCBpcyBhdCBtb3N0IDIwLDAwMCwwMDAuPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMSI6Ijx1bD5cclxuXHQ8bGk+MSAmbGU7IHggJmxlOyA1MDA8XC9saT5cclxuPFwvdWw+XHJcbiIsInN1YnRhc2syIjoiPHVsPlxyXG5cdDxsaT4xICZsZTsgeCAmbGU7IDMwMCwwMDA8XC9saT5cclxuPFwvdWw+XHJcbiJ9XQ==

채점

  • 예제는 채점하지 않는다.