O(n)。

C++ 代码

//0:6根 不能最高位
//1:2根
//2:5根(可以优化掉3和5) 
//4:4根
//6:6根 最高位用(可以优化掉9)
//7:3根
//8:7根 (n比较大的时候后面位全用8占位)
using namespace std;
string A[22]={"-1","-1","1","7","4","2","6","8","10","18","22","20","28","68","88","108","188","200","208","288","688","888"};
//             0    1    2   3   4   5   6   7   8    9    10   11   12   13   14   15    16    17    18    19    20    21
int main(){
    int T,n;
    cin>>T;
    for(int I=1;I<=T;I++){
        cin>>n;
        if(n<=21){
            cout<<A[n]<<endl;
        }
        else{
            n--;
            int m=n/7-2;
            n%=7;
            n+=15;
            cout<<A[n];
            for(int i=1;i<=m;i++){
                printf("8");
            }
            if(n>5000&&n%7>3)cout<<"0";
            cout<<endl; 
        }
    }
}