1202_D. Print a 1337-string...
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.

Input

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

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

Output

For the i-th query print one string s_i (1 ≤ |s_i| ≤ 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
```python
import sys

t = int(sys.stdin.readline().strip())
for i in range(0, t):
    n = int(sys.stdin.readline().strip())
    c = 4 * 10 ** 2
    d = n // (c * (c-1) // 2)
    b = n % (c * (c-1) // 2)

    print("133" + "7"*b + "3" * (c-2) + "7"*d)

```