codeforces#P1202D. Print a 1337-string...

    ID: 30380 远端评测题 1000ms 256MiB 尝试: 0 已通过: 0 难度: 6 上传者: 标签>combinatoricsconstructive algorithmsmathstrings*1900

Print a 1337-string...

Description

The subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

You are given an integer $n$.

You have to find a sequence $s$ consisting of digits $\{1, 3, 7\}$ such that it has exactly $n$ subsequences equal to $1337$.

For example, sequence $337133377$ has $6$ subsequences equal to $1337$:

  1. $337\underline{1}3\underline{3}\underline{3}7\underline{7}$ (you can remove the second and fifth characters);
  2. $337\underline{1}\underline{3}3\underline{3}7\underline{7}$ (you can remove the third and fifth characters);
  3. $337\underline{1}\underline{3}\underline{3}37\underline{7}$ (you can remove the fourth and fifth characters);
  4. $337\underline{1}3\underline{3}\underline{3}\underline{7}7$ (you can remove the second and sixth characters);
  5. $337\underline{1}\underline{3}3\underline{3}\underline{7}7$ (you can remove the third and sixth characters);
  6. $337\underline{1}\underline{3}\underline{3}3\underline{7}7$ (you can remove the fourth and sixth characters).

Note that the length of the sequence $s$ must not exceed $10^5$.

You have to answer $t$ independent queries.

The first line contains one integer $t$ ($1 \le t \le 10$) — the number of queries.

Next $t$ lines contains a description of queries: the $i$-th line contains one integer $n_i$ ($1 \le n_i \le 10^9$).

For the $i$-th query print one string $s_i$ ($1 \le |s_i| \le 10^5$) consisting of digits $\{1, 3, 7\}$. String $s_i$ must have exactly $n_i$ subsequences $1337$. If there are multiple such strings, print any of them.

Input

The first line contains one integer $t$ ($1 \le t \le 10$) — the number of queries.

Next $t$ lines contains a description of queries: the $i$-th line contains one integer $n_i$ ($1 \le n_i \le 10^9$).

Output

For the $i$-th query print one string $s_i$ ($1 \le |s_i| \le 10^5$) consisting of digits $\{1, 3, 7\}$. String $s_i$ must have exactly $n_i$ subsequences $1337$. If there are multiple such strings, print any of them.

Samples

2
6
1
113337
1337