시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 3 3 3 100.000%

문제

R이 주어졌을 때, 마지막 R자리가 1과 2로만 이루어진 가장 작은 2k를 구하는 프로그램을 작성하시오. 

예를 들어, 29 = 512이고, 289 = 618970019642690137449562112 이다. 29는 마지막 2자리가 1과 2로 이루어져 있고, 289는 마지막 4가지가 1과 2로만 이루어져 있다.

R이 6일때까지 답을 구해보면 다음과 같다.

R 가장 작은 k 2k
1 1 2
2 9 512
3 89 ...112
4 89 ...2112
5 589 ...22112
6 3089 ...122112

입력

첫째 줄에 테스트 케이스의 개수 T(1<=T<=50)가 주어진다. 각 테스트 케이스는 정수 1개로 이루어져 있고, 이 수는 R(1<=R<=20)이다. 

출력

각 테스트 케이스에 대해 한 줄에 하나씩 마지막 R자리 1과 2로만 이루어진 가장 2k의 k를 출력한다.

예제 입력 1

6
1
2
4
5
7
15

예제 출력 1

1
9
89
589
3089
11687815589 
W3sicHJvYmxlbV9pZCI6IjI3MDkiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIEsiLCJkZXNjcmlwdGlvbiI6IjxwPlxyXG5cdFJcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViOWM4XHVjOWMwXHViOWM5IFJcdWM3OTBcdWI5YWNcdWFjMDAgMVx1YWNmYyAyXHViODVjXHViOWNjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIDI8c3VwPms8XC9zdXA+XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCAyPHN1cD45PFwvc3VwPiA9IDUxMlx1Yzc3NFx1YWNlMCwgMjxzdXA+ODk8XC9zdXA+ID0gNjE4OTcwMDE5NjQyNjkwMTM3NDQ5NTYyMTEyIFx1Yzc3NFx1YjJlNC4gMjxzdXA+OTxcL3N1cD5cdWIyOTQgXHViOWM4XHVjOWMwXHViOWM5IDJcdWM3OTBcdWI5YWNcdWFjMDAgMVx1YWNmYyAyXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWFjZTAsIDI8c3VwPjg5PFwvc3VwPlx1YjI5NCBcdWI5YzhcdWM5YzBcdWI5YzkgNFx1YWMwMFx1YzljMFx1YWMwMCAxXHVhY2ZjIDJcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0Ulx1Yzc3NCA2XHVjNzdjXHViNTRjXHVhZTRjXHVjOWMwIFx1YjJmNVx1Yzc0NCBcdWFkNmNcdWQ1NzRcdWJjZjRcdWJhNzQgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1YjJlNC48XC9wPlxyXG5cclxuPHRhYmxlIGNsYXNzPVwidGFibGUgdGFibGUtYm9yZGVyZWRcIiBzdHlsZT1cIndpZHRoOjYwJTtcIj5cclxuXHQ8dGhlYWQ+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0aCBzdHlsZSA9IFwid2lkdGg6MjAlO1wiPlxyXG5cdFx0XHRcdFI8XC90aD5cclxuXHRcdFx0PHRoIHN0eWxlID0gXCJ3aWR0aDoyMCU7XCI+XHJcblx0XHRcdFx0XHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBrPFwvdGg+XHJcblx0XHRcdDx0aCBzdHlsZSA9IFwid2lkdGg6MjAlO1wiPlxyXG5cdFx0XHRcdDI8c3VwPms8XC9zdXA+PFwvdGg+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90aGVhZD5cclxuXHQ8dGJvZHk+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0XHQxPFwvdGQ+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0XHQxPFwvdGQ+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0XHQyPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHRcdDI8XC90ZD5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHRcdDk8XC90ZD5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHRcdDUxMjxcL3RkPlxyXG5cdFx0PFwvdHI+XHJcblx0XHQ8dHI+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0XHQzPFwvdGQ+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0XHQ4OTxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdFx0Li4uMTEyPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHRcdDQ8XC90ZD5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHRcdDg5PFwvdGQ+XHJcblx0XHRcdDx0ZD5cclxuXHRcdFx0XHQuLi4yMTEyPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHRcdDx0cj5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHRcdDU8XC90ZD5cclxuXHRcdFx0PHRkPlxyXG5cdFx0XHRcdDU4OTxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdFx0Li4uMjIxMTI8XC90ZD5cclxuXHRcdDxcL3RyPlxyXG5cdFx0PHRyPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdFx0NjxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdFx0MzA4OTxcL3RkPlxyXG5cdFx0XHQ8dGQ+XHJcblx0XHRcdFx0Li4uMTIyMTEyPFwvdGQ+XHJcblx0XHQ8XC90cj5cclxuXHQ8XC90Ym9keT5cclxuPFwvdGFibGU+XHJcblxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWFjMWNcdWMyMTggVCgxJmx0Oz1UJmx0Oz01MClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWM4MTVcdWMyMTggMVx1YWMxY1x1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVhY2UwLCBcdWM3NzQgXHVjMjE4XHViMjk0IFIoMSZsdDs9UiZsdDs9MjApXHVjNzc0XHViMmU0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWI5YzhcdWM5YzBcdWI5YzkgUlx1Yzc5MFx1YjlhYyAxXHVhY2ZjIDJcdWI4NWNcdWI5Y2MgXHVjNzc0XHViOGU4XHVjNWI0XHVjOWM0IFx1YWMwMFx1YzdhNSAyPHN1cD5rPFwvc3VwPlx1Yzc1OCBrXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIyNzA5IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVGhlIFR3byBOb3RlIFJhZyIsImRlc2NyaXB0aW9uIjoiPHA+U2luY2UgbW9zdCBjb21wdXRlcnMgYXJlIGJpbmFyeSBtYWNoaW5lcywgYm90aCBwb3dlcnMgb2YgdHdvIGFuZCBwcm9ibGVtcyB0aGF0IGludm9sdmUgb25seSB0d28gdmFsdWVzIGFyZSBpbXBvcnRhbnQgdG8gY29tcHV0ZXIgc2NpZW50aXN0cy4gVGhlIGZvbGxvd2luZyBwcm9ibGVtIGhhcyB0byBkbyB3aXRoIHBvd2VycyBvZiB0d28gYW5kIHRoZSBkaWdpdHMgMSBhbmQgMi48XC9wPlxyXG5cclxuPHA+U29tZSBwb3dlcnMgb2YgdHdvIGFzIGRlY2ltYWwgdmFsdWVzLCBzdWNoIGFzIDI8c3VwPjk8XC9zdXA+ID0gNTEyIGFuZCAyPHN1cD44OTxcL3N1cD4gPSA2MTgsOTcwLDAxOSw2NDIsNjkwLDEzNyw0NDksNTYyLDExMiBlbmQgaW4gYSBzdHJpbmcgb2YgZGlnaXRzIGNvbnNpc3Rpbmcgb25seSBvZiAxJiMzOTtzIGFuZCAyJiMzOTtzICgxMiBmb3IgMjxzdXA+OTxcL3N1cD4gYW5kIDIxMTIgZm9yIDI8c3VwPjg5PFwvc3VwPikuIEluIGZhY3QsIGl0IGNhbiBiZSBwcm92ZWQgdGhhdDo8XC9wPlxyXG5cclxuPGJsb2NrcXVvdGU+XHJcbjxwPkZvciBldmVyeSBpbnRlZ2VyIFIsIHRoZXJlIGV4aXN0cyBhIHBvd2VyIG9mIDIgc3VjaCB0aGF0IDI8c3VwPks8XC9zdXA+IHVzZXMgb25seSB0aGUgZGlnaXRzIDEgYW5kIDIgaW4gaXRzIGxhc3QgUiBkaWdpdHMuPFwvcD5cclxuPFwvYmxvY2txdW90ZT5cclxuXHJcbjxwPlRoaXMgaXMgc2hvd24gYSBiaXQgbW9yZSBjbGVhcmx5IGluIHRoZSBmb2xsb3dpbmcgdGFibGU6PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvdHdvcmFnLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0OjE5MXB4OyB3aWR0aDoyOTdweFwiIFwvPjxcL3A+XHJcblxyXG48cD5Zb3VyIGpvYiBpcyB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCB3aWxsIGRldGVybWluZSwgZm9yIGdpdmVuIFIsIHRoZSBzbWFsbGVzdCBLIHN1Y2ggdGhhdCAyPHN1cD5LPFwvc3VwPiBlbmRzIGluIGEgc3RyaW5nIG9mIFIgZGlnaXRzIGNvbnRhaW5pbmcgb25seSAxJiMzOTtzIGFuZCAyJiMzOTtzLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgdGhlIGlucHV0IGNvbnRhaW5zIGEgc2luZ2xlIGRlY2ltYWwgaW50ZWdlciwgTiwgMSAmcG91bmQ7IE4gJnBvdW5kOyA1MCwgdGhlIG51bWJlciBvZiBwcm9ibGVtIGRhdGEgc2V0cyB0byBmb2xsb3cuIEVhY2ggZGF0YSBzZXQgY29uc2lzdHMgb2YgYSBzaW5nbGUgaW50ZWdlciBSLCAxICZwb3VuZDsgUiAmcG91bmQ7IDIwLCBmb3Igd2hpY2ggd2Ugd2FudCBhIHBvd2VyIG9mIDIgZW5kaW5nIGluIGEgc3RyaW5nIG9mIFIgMSYjMzk7cyBhbmQgMiYjMzk7cy48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhIHNldCwgeW91IHNob3VsZCBnZW5lcmF0ZSBvbmUgbGluZSBvZiBvdXRwdXQgd2l0aCB0aGUgZm9sbG93aW5nIHZhbHVlczogVGhlIGRhdGEgc2V0IG51bWJlciBhcyBhIGRlY2ltYWwgaW50ZWdlciAoc3RhcnQgY291bnRpbmcgYXQgb25lKSwgYSBzcGFjZSwgdGhlIGlucHV0IHZhbHVlIFIsIGFub3RoZXIgc3BhY2UsIGFuZCB0aGUgc21hbGxlc3QgdmFsdWUgSyBmb3Igd2hpY2ggMjxzdXA+SzxcL3N1cD4gZW5kcyBpbiBhIHN0cmluZyBvZiBSIDEmIzM5O3MgYW5kIDImIzM5O3MuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d