Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

D. Print a 1337-string...

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThe 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$$$:

- $$$337\underline{1}3\underline{3}\underline{3}7\underline{7}$$$ (you can remove the second and fifth characters);
- $$$337\underline{1}\underline{3}3\underline{3}7\underline{7}$$$ (you can remove the third and fifth characters);
- $$$337\underline{1}\underline{3}\underline{3}37\underline{7}$$$ (you can remove the fourth and fifth characters);
- $$$337\underline{1}3\underline{3}\underline{3}\underline{7}7$$$ (you can remove the second and sixth characters);
- $$$337\underline{1}\underline{3}3\underline{3}\underline{7}7$$$ (you can remove the third and sixth characters);
- $$$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.

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.

Example

Input

2 6 1

Output

113337 1337

Codeforces (c) Copyright 2010-2019 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/19/2019 20:41:51 (h1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|