Background

In Season 119, May, when it should have been spring with cherry blossoms in full bloom, Gensokyo was still covered by heavy snow. The mastermind behind this incident, Saigyouji Yuyuko, read in an ancient book that if the youkai cherry tree Saigyou Ayakashi were to fully bloom, someone would be revived. Out of curiosity, she ordered Youmu to collect the "spring" of Gensokyo and single-handedly planned this incident. During the process of collecting spring, the scattered energy, influenced by Saigyou Ayakashi, turned into "sakura points" and spread across Gensokyo. This incident is called the "Spring Snow Incident".

The three protagonists who set out to resolve the incident—Hakurei Reimu, Kirisame Marisa, and Izayoi Sakuya—each with different goals, began their journey to find the mastermind. During this process, they discovered something called the "Senluo Barrier". Once enough sakura points are collected, a Senluo Barrier will open immediately. After it opens, it can briefly block all attacks and provide corresponding buffs.

However, perhaps due to a bug in the world's order, if too many Senluo Barriers are opened, the numeric display will break: the Senluo Barrier information, which should have been a number, will be replaced by Chinese characters. To solve these strange problems, they came to you, hoping you can help them fix this issue.

Problem Description

Brief Statement

Given ASCII art of Chinese characters and the number of $\texttt{*}$ you can use, output the largest Chinese numeral (you do not have to use all the $\texttt{*}$). Do not consider place-value units such as "thousand" or "hundred".

Original Statement

The information display system for the Senluo Barrier can be viewed as a rectangular system with width $7$ and infinite length, containing only two characters: $\texttt{.}$ and $\texttt{*}$.

Because the protagonist group lost their memory, they opened too many Senluo Barriers while resolving the incident, causing the position that should display digits to become Chinese characters instead. In the display system, each Chinese numeral (only zero, one, two through nine) is shown in a dot-matrix font.

Clearly, reading Chinese characters is much harder than reading plain digits. However, the display system tells the protagonists that there are $n$ $\texttt{*}$ on the display. They want to know: using no more than $n$ $\texttt{*}$, what is the maximum number that can be represented on the display, to help them resolve the incident?

For convenience in judging and reading, you only need to output the corresponding integer.

---

Below are the pictures of the ASCII art, and also the text form. In the provided files, we also prepared the text form of the ASCII art for each digit.

.......  .......  .......  *******  .......  .......  .......  .......  ..*....  *******
.......  .......  ..***..  *.*.*.*  *******  ...*...  ...*...  ..*.*..  ..*....  *.....*
.......  ..***..  .......  *.*.*.*  ...*...  ...*...  ...*...  ..*.*..  *****..  *.....*
.*****.  .......  .*****.  **...**  .******  .*****.  *******  ..*.*..  ..*.*..  *.....*
.......  .......  .......  *.....*  ...*..*  ..*.*..  ...*...  .*...*.  ..*.*..  *.....*
.......  .*****.  *******  *.....*  *******  .*...*.  ...*..*  *.....*  .*..*.*  *.....*
.......  .......  .......  *******  .......  .......  ...****  .......  *...***  *******

Input Format

Input a positive integer $n$, representing the number of $\texttt{*}$ the protagonist group has.

Output Format

Output an integer, representing the maximum number that can be formed. Since Chinese characters are inconvenient to output, you only need to output the integer corresponding to the Chinese numerals.

5

1

13

21

Hint

Sample Explanation

For sample $1$, obviously you can only form the number one, so output $1$.

For sample $2$, you can form many numbers such as "one two" and "six", but among them the largest number is $21$. It is also clear that there is no larger number that can be formed.

Constraints

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|}\hline \textbf{Subtask} & \bm{n\le} & \textbf{Score}\\\hline 1 & 10 & 5\\\hline 2 & 100 & 15 \\\hline 3 & 10^3 & 20 \\\hline 4 & 10^6 & 60 \\\hline \end{array}$$

For all data, it is guaranteed that $5 \leq n \leq 10^6$.

Translated by ChatGPT 5