시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.5 초 256 MB 30 13 6 66.667%

문제

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

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

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

입력

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

출력

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

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

제한

  • 1 ≤ T ≤ 100

서브태스크 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+MSAmbGU7IFQgJmxlOyAxMDA8XC9saT5cclxuPFwvdWw+XHJcbiIsInN1YnRhc2sxIjoiPHVsPlxyXG5cdDxsaT4xICZsZTsgeCAmbGU7IDUwMDxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazIiOiI8dWw+XHJcblx0PGxpPjEgJmxlOyB4ICZsZTsgMzAwLDAwMDxcL2xpPlxyXG48XC91bD5cclxuIn0seyJwcm9ibGVtX2lkIjoiMTc0MzEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJHYW1lIiwiZGVzY3JpcHRpb24iOiI8cD5BbGJlcnQgaXMgcGxheWluZyBhIGdhbWUgd2l0aCBudW1iZXJzLiBUbyBwbGF5IHRoZSBnYW1lLCBoZSBuZWVkcyB0d28gc2hlZXRzJm5ic3A7b2YgcGFwZXIsIG9uZSBpbiBibHVlIGFuZCBhbm90aGVyIGluIHJlZC4gQXQgZmlyc3QsIGJvdGggc2hlZXRzIGhhdmUgbnVtYmVyICZxdW90OzEmcXVvdDsgd3JpdHRlbiBvbiB0aGVtLjxcL3A+XHJcblxyXG48cD5BbGJlcnQgcGxheXMgdGhlIGdhbWUgYXMgZm9sbG93cy4gRmlyc3QgaGUgY2FsY3VsYXRlcyB0aGUgc3VtIG9mIHRoZSB0d28gbnVtYmVycyB3cml0dGVuIG9uIHRoZSBzaGVldHMuIEhlIHRoZW4gcmVwbGFjZXMgdGhlIG51bWJlciBvbiBvbmUgb2YgdGhlIHNoZWV0cyBieSB0aGlzIHN1bS4gT25lIHN1Y2ggbW92ZSBpcyBjYWxsZWQgYW4gJnF1b3Q7YWRkaXRpb24mcXVvdDsuIEFmdGVyIGFwcGx5aW5nIGFkZGl0aW9uKHMpLCBBbGJlcnQgZW5kcyB0aGUgZ2FtZSB3aGVuIG9uZSBvZiB0aGUgc2hlZXRzIGhhcyB4IHdyaXR0ZW4gb24gaXQgKHRoZSBudW1iZXIgaGUgaW5pdGlhbGx5IGNob29zZXMgdG8gcGxheSB0aGlzIGdhbWUpLjxcL3A+XHJcblxyXG48cD5Gb3IgZXZlcnkgaW50ZWdlciB4ICZndDsgMSwgaWYgQWxiZXJ0IGNob29zZXMgdG8gd3JpdGUgb25seSBvbiB0aGUgc2FtZSBjb2xvciBzaGVldCwgdGhlbiBhZnRlciAoeC0xKSBhZGRpdGlvbnMgdGhlIGdhbWUgYWx3YXlzIGVuZHMuIEFsYmVydCB3YW50cyB0byBrbm93IHRoZSBtaW5pbXVtIG51bWJlciBvZiBhZGRpdGlvbnMgaGUgbmVlZHMgdG8gcGVyZm9ybSBpbiBvcmRlciB0byByZWFjaCB4LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgd2lsbCBjb250YWluIFQsIHRoZSBudW1iZXIgb2YgdGVzdCBjYXNlcy48XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgbmV4dCBUIGxpbmVzIHdpbGwgY29udGFpbiBhIHNpbmdsZSBpbnRlZ2VyIHguPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCB5b3UgbXVzdCBvdXRwdXQgYSBzdHJpbmcgdGhhdCBkZXNjcmliZXMgaG93IEFsYmVydCBjYW4gcmVhY2ggeCB3aXRoIG1pbmltdW0gbnVtYmVyIG9mIGFkZGl0aW9ucy48XC9wPlxyXG5cclxuPHA+SWYgTSBpcyB0aGUgbWluaW11bSBudW1iZXIgb2YgYWRkaXRpb25zIEFsYmVydCBtdXN0IGRvIGluIG9yZGVyIHRvIGdldCB4LCB0aGVuIHRoZSBvdXRwdXQgbXVzdCBiZSBhIHN0cmluZyBvZiBsZW5ndGggTS4gRWFjaCBjaGFyYWN0ZXIgc2hvdWxkIGJlIGVpdGhlciBCIG9yIFIgZGVwZW5kaW5nIG9uIHdoaWNoIGNvbG9yZWQgc2hlZXQgQWxiZXJ0IG11c3Qgd3JpdGUgdGhlIHN1bW1lZCBudW1iZXIgb24uIElmIHRoZXJlIGFyZSBtdWx0aXBsZSB3YXlzIHRvIGFjaGlldmUgdGhlIG1pbmltdW0gbnVtYmVyIG9mIGFkZGl0aW9ucywgeW91IG1heSBvdXRwdXQgYW55IG9uZSBvZiB0aGVtLjxcL3A+XHJcbiIsImhpbnQiOiI8cD5XaGVuIHggPSA1LCB0aGVyZSBhcmUgbWFueSB3YXlzIHRvIHJlYWNoIDUuPFwvcD5cclxuXHJcbjxwPkIgcmVwcmVzZW50cyBibHVlIHNoZWV0IGFuZCBSIHJlcHJlc2VudHMgcmVkIHNoZWV0LiBUaGUgbnVtYmVyIGFmdGVyIEIgb3IgUiByZXByZXNlbnRzIHRoZSBudW1iZXIgd3JpdHRlbiBvbiB0aGUgcmVzcGVjdGl2ZSBzaGVldC48XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT4oQjEsIFIxKSAtJmd0OyBBbGJlcnQgY2hvb3NlcyBCIC0mZ3Q7IChCMiwgUjEpIC0mZ3Q7IEFsYmVydCBjaG9vc2VzIFIgLSZndDsgKEIyLCBSMykgLSZndDsgQWxiZXJ0IGNob29zZXMgQiAtJmd0OyAoQjUsIFIzKSAtJmd0OyBHYW1lIGVuZHMgKDMgYWRkaXRpb25zKS48XC9saT5cclxuXHQ8bGk+KEIxLCBSMSkgLSZndDsgQWxiZXJ0IGNob29zZXMgQiAtJmd0OyAoQjIsIFIxKSAtJmd0OyBBbGJlcnQgY2hvb3NlcyBCIC0mZ3Q7IChCMywgUjEpIC0mZ3Q7IEFsYmVydCBjaG9vc2VzIEIgLSZndDsgKEI0LCBSMSkgLSZndDsgQWxiZXJ0IGNob29zZXMgQiAtJmd0OyAoQjUsIFIxKSAtJmd0OyBHYW1lIGVuZHMgKDQgYWRkaXRpb25zKS48XC9saT5cclxuPFwvdWw+XHJcbiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0IiwibGltaXQiOiI8dWw+XHJcblx0PGxpPjEgJmxlOyBUICZsZTsgMTAwPFwvbGk+XHJcblx0PGxpPjEgJmxlOyB4ICZsZTsgMzAwLDAwMDxcL2xpPlxyXG48XC91bD5cclxuIiwic3VidGFzazEiOiI8dWw+XHJcblx0PGxpPjEgJmxlOyB4ICZsZTsgNTAwPFwvbGk+XHJcbjxcL3VsPlxyXG4iLCJzdWJ0YXNrMiI6Ijx1bD5cclxuXHQ8bGk+MSAmbGU7IHggJmxlOyAzMDAsMDAwPFwvbGk+XHJcbjxcL3VsPlxyXG4ifV0=

채점

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