## Problem: Sherlock and The Beast

Sherlock Holmes is getting paranoid about Professor Moriarty, his archenemy. All his efforts to subdue Moriarty have been in vain. These days Sherlock is working on the conversation he had with Dr. Watson. Watson mentioned that the CIA have been having weird problems with their supercomputer ‘The Beast’ recently.

This afternoon, Sherlock received a note from Moriarty, saying he has infected ‘The Beast’ with a virus. In addition the note had the number ‘k’ printed on it. After doing some calculations, Sherlock found out that the key to remove the virus is the largest ‘Decent’ Number having ‘k’ digits.

A ‘Decent’ Number has –
1. Only 3 and 5 as its digits.
2. Number of times 3 appears is divisible by 5.
3. Number of times 5 appears is divisible by 3.

Meanwhile, the counter to destruction of ‘The Beast’ is running very fast. Can you save ‘The Beast’ and find the key before Sherlock?

Input Format
1st line will contain an integer T, the number of test cases, followed by T lines, each line containing an integer N i.e. the number of digits in the number

Output Format
Largest Decent number having N digits. If no such number exists, you tell Sherlock that he is wrong and print ‘-1’

Constraints
1<=T<=20
1<=N<=100000

Sample Input

``````4
1
3
5
11
``````

Sample Output

``````-1
555
33333
55555533333
``````

Explanation
For N=1 , there is no such number.
for N=3, 555 is only possible number.
For N=5, 33333 is only possible number.
For N=11 , 55555533333 and all of permutations of digits are valid numbers, among them, the given number is the largest one.

#include <stdio.h>

void Decent_Number(long n);

int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
int T,i;
long N,a[100];
scanf(“%d”,&T);
for(i=0;i<T;++i)
scanf(“%ld”,&a[i]);
for(i=0;i<T;++i){
Decent_Number(a[i]);
if(i!=T-1)
printf(“\n”);
}
return 0;
}

void Decent_Number(long n){
long i,j,temp,breakpoint,k;
/*First case: N is divisible by 3, so we just print N number of 5*/
if(n%3==0){
for(j=1;j<=n;++j)
printf(“5”);
return;
}
/*This is second situation: N subtract 5, divisible by 3 and must bigger than zero*/
if((n-5)%3==0&&(n-5)>0){
for(j=1;j<=n-5;++j)
printf(“5”);
for(j=1;j<=5;++j)
printf(“3”);
return;
}
/*Third case: Seem like second case but N subtract for 10*/
if((n-10)%3==0&&(n-10)>0){
for(j=1;j<=n-10;++j)
printf(“5”);
for(j=1;j<=10;++j)
printf(“3”);
return;
}
/*The last case: Not as special,eazy as cases above*/
for(i=1;i<=n;++i){
temp=n-i;
if(i%3==0&&temp%5==0){
if((i+1)%5==0&&(temp-1)%3==0){
for(j=1;j<=temp-1;++j)
printf(“5”);
for(j=1;j<=i+1;++j)
printf(“3”);
return;
}
if(temp%3==0&&i%5==0){
for(j=1;j<=n-i;++j)
printf(“5”);
for(j=1;j<=i;++j)
printf(“3”);
return;
}
if(temp%3!=0){
for(j=1;j<=i;++j)
printf(“5”);
for(j=1;j<=temp;++j)
printf(“3”);
return;
}
}
if(i%5==0&&temp%3==0&&temp%5==0){
for(j=1;j<=temp;++j)
printf(“5”);
for(j=1;j<=i;++j)
printf(“3”);
return;
}
/*you can rewrite this fragment so that it can be shorter, because there are somethings that described on the top of this function*/
if(i==n||i==(n-1)){
if((n%3)==0&&(n%5)!=0||(n%3)==0&&(n%5)==0){
for(j=1;j<=n;++j)
printf(“5”);
return;
}
else if((n%5)==0&&(n%3)!=0){
for(j=1;j<=n;++j)
printf(“3”);
return;
}
else{
printf(“-1”);
return;
}
}
/*This fragment can be deleted (just leave two lines in the last “else”)*/
}
}