" '죽음의 나라'의 왕인 〔死王〕은 민심을 알아보기 위해 일반 백성으로 변장하고 나라를 시찰하였다. 그런데 〔死王〕이 가는 곳마다 백성이 자신의 험담을 하고 있었다. 이에 분노한 〔死王〕은 (고칠 생각을 해야 하는데…) 법을 만들어서 백성이 자신의 험담을 하는 것을 통제하였다. 법이 공포되자, 백성은 수에 〔死王〕의 상징인 수 '4444'를 집어넣어 편지나 쪽지를 보내는 방법으로 〔死王〕을 험담하였다. …"

우연히 이 이야기를 들은 철수는 자연수 중 "4444"가 포함된 수들을 "〔死王〕의 수"라고 정의하였다. 예로 4444, 14444, 194444429 모두 〔死王〕의 수이다. 철수는 이 수들의 특징이 궁금해서 〔死王〕의 수를 오름차순으로 나열하다가, 33번째 즈음에 지쳐서 포기하였다.

철수는 작은 순으로 N 번째 〔死王〕의 수를 구하는 프로그램을 작성해 달라고 부탁했다. 부상은 "더블릿 푼 문제 수 1개 추가"이다.

(참고로 〔死王〕은 염라대왕입니다….)

입력

첫 번째 줄에 테스트 케이스의 개수 T(1≤T≤5000)가 주어진다.

i+1(1≤i≤T)번째 줄에 N[i] (1≤N[i]≤100,000,000) 가 주어진다.

출력

i번째 줄에 작은 순으로 N[i] 번째 〔死王〕의 수를 출력한다.

입출력 예

입력

3
1
2
6

출력

4444
14444
44441

입력

7
5
9
12
17
22
29
31

출력

44440
44444
44447
74444
124444
144445
144447

입출력 보충

작은 순으로 1~15번째 〔死王〕의 수를 나열하면 아래와 같다.

4444, 14444, 24444, 34444, 44440, 44441, 44442, 44443, 44444, 44445, 44446, 44447, 44448, 44449, 54444

작은 순으로 100,000,000번째 〔死王〕의 수는 142463444480이다.

출처: tncks0121