애런슨 수열

시간 제한2초메모리 제한128 MB

요약

각 항을 서수로 나열한 자기지시 문장에서 k번째 T 글자의 위치를 구해 아론슨 수열의 항을 계산한다.

문제

애런슨 수열 $a_k$ 는 자기 자신을 가리키는 다음 문장으로 정의됩니다.

"T is the first, fourth, eleventh, ... letter of this sentence." (T는 이 문장의 첫 번째, 네 번째, 열한 번째, ... 글자이다.)

... 부분은 문장이 스스로에 대해 참이 되도록 채워집니다. 이 문장에서 글자만 세면(공백, 문장부호, 숫자는 무시하고 대소문자도 구분하지 않습니다), $a_k$ 는 글자 T가 $k$ 번째로 나타나는 위치입니다. 처음 몇 개 값은 다음과 같습니다.

$1,\ 4,\ 11,\ 16,\ 24,\ 29,\ 33,\ 35,\ 39,\ \dots$

$k \le 100000$ 일 때 $a_k \le 1000000$ 임이 알려져 있습니다.

문장을 구성하려면 서수(ordinal)를 영어로 적을 수 있어야 합니다. 서수(first, second, third, …)는 기수(cardinal; one, two, three, …)로부터 정의되므로 기수를 먼저 설명합니다.

20 미만의 기수는 한 단어입니다 (3 → three, 17 → seventeen).
20 이상 99 이하의 기수는 십의 자리 단어 뒤에 0이 아닌 일의 자리 단어를 붙입니다 (40 → forty, 56 → fifty six).
100 이상 999 이하의 기수는 백의 자리 부분 뒤에 0이 아닌 나머지를 붙입니다 (100 → one hundred, 117 → one hundred seventeen, 640 → six hundred forty, 999 → nine hundred ninety nine).
1000 이상 999999 이하의 기수는 천의 자리 부분 뒤에 0이 아닌 나머지를 붙입니다 (12345 → twelve thousand three hundred forty five).

서수는 기수와 똑같이 적되 마지막 단어만 서수형으로 바꿉니다.

3rd → third, 56th → fifty sixth, 100th → one hundredth, 12345th → twelve thousand three hundred forty fifth.

입력은 여러 개의 질의로 이루어집니다. 각 질의는 한 줄에 양의 정수 $k$ 하나입니다 ( $1 \le k \le 100000$ ). 질의로 주어지는 $k$ 값은 비내림차순(non-decreasing)으로 주어집니다. 입력의 끝은 0 하나만 있는 줄로 표시됩니다.

각 질의 $k$ 에 대해 $a_k$ 의 값을 한 줄에 출력합니다. 모든 $a_k$ 는 $1000000$ 이하입니다.