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

Difficulty: interview

Starter code:

Solutions:
# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
# TAIWAN NUMBER ONE!!!!!!!!!!!!!!!!!!!
from sys import stdin, stdout
from itertools import accumulate

T = int(input())
#s = input()
#N,M,K,Q = [int(x) for x in stdin.readline().split()]
#arr = [int(x) for x in stdin.readline().split()]

check = [0]*45000

s = 0
for i in range(1,45001):
    s += i
    check[i-1] = s

for i in range(T):
    N = int(input())

    if N in check:
        idx = check.index(N)
        idx += 2
        print('1','3'*idx,'7',sep='',end='\n')

    else:
        # find largest number < N in check
        target = max(num for num in check if num < N)
        three = check.index(target)

        d = N - target

        print('1','3'*2,'7'*d,'3'*(three),'7',sep='',end='\n')

import sys
import math
input = sys.stdin.readline

arr=[]
for i in range(1,100000):
	arr.append(i*(i+1)//2)

def bs(l, r, x):
	if r>=l:
		mid = l + (r-l)//2
		if arr[mid]<=x and arr[mid+1]>x:
			return mid

		elif arr[mid]>x:
			return bs(l, mid-1, x)

		else:
			return bs(mid+1, r, x)

t=int(input())
for i in range(t):
	n=int(input())

	d=bs(0,len(arr)-1,n)
	diff=n-arr[d]
	#print(d,diff)

	ans=["1","3","3"]
	for j in range(diff):
		ans.append("7")
	for j in range(d):
		ans.append("3")
	ans.append("7")

	print(''.join(ans))


def closest(arr,pos):
	n = len(arr)
	low = 0
	up = n-1
	while(up >= low):
	  mid = (up+low)//2
	  ##print(mid)
	  if(arr[mid] == pos):
	  	return mid
	  elif(arr[mid] > pos):
	  	if(arr[mid-1] < pos):
	  		return mid-1
	  	else:    
	  		up = mid - 1
	  else:
	  	if(arr[mid+1] > pos):
	  		return mid
	  	else:
	  		low = mid + 1


t = int(input())
n = 1
a = []
while(n<100000):
	a.append(n*(n+1)//2)
	n += 1

for i in range(t):
	n = int(input())
	s = ['1','3','3']
	no3 = closest(a,n)
	no7 = n - a[no3]
	#print(no3,no7)
	s.extend(['7']*no7)
	s.extend(['3']*no3)
	s.append('7')
	print(''.join(s))


import sys
from collections import defaultdict
input = sys.stdin.readline
import math


def main():
    t = int(input())
    for _ in range(t):
        ni = int(input())
        cnt3 = 2
        while (cnt3*(cnt3+1))//2 <= ni:
            cnt3 += 1
        rest = ni-(cnt3*(cnt3-1)//2)
        print('1'+'33'+'7'*rest+'3'*(cnt3-2)+'7')


def __starting_point():
    main()


__starting_point()

t=int(input())
while(t):
    n=int(input())
    ch=0
    
    for i in range(100000):
        if((i*(i-1)//2)>n):
            ch=i-1
            #print(ch)
            break
        
    rem=n-(ch*(ch-1))//2
    
    s="1"
    
    s=s+"33"+"7"*rem+"3"*(ch-2)+"7"
    
    print(s)
    
    t-=1