시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 2 2 2 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를 출력한다.

예제 입력

6
1
2
4
5
7
15

예제 출력

1
9
89
589
3089
11687815589 

힌트