#1626 수열 규칙 찾기

45  1 s   128 MB  

Description

다음과 같은 수열에 대한 규칙을 파악한 다음, 정수 N이 입력되었을 때 SN을 출력하는 프로그램을 작성하라.

S1 : 1
S2 : 11
S3 : 12
S4 : 1121
S5 : 1321

Input

입력의 첫 줄에는 테스트 케이스를 뜻하는 T(1<=T<=50) 가 입력된다.
그 다음 줄 부터 T개의 정수 N이 입력된다.

Output

각 N에 대해서 SN을 출력한다.

Sample Input

Sample Output

5
1
2
3
4
5
1
11
12
1121
1321