NITK02 - HACKERS AND KILLER NUMBER
Recently RAW have been having weird problems with their supercomputer 'The PARAM'. Today, They recieved a note from hackers that they have infected 'The PARAM' with a virus. In addition the note had the number 'k' printed on it. After doing some calculations, RAW agents found out that the only way to remove that virus is the largest 'Killer' Number having 'k' digits.
A 'Killer' Number has:
- Only 3 and 5 as its digits.
- Number of times 3 appears is divisible by 5.
- Number of times 5 appears is divisible by 3.
Meanwhile, the counter to destruction of ‘The PARAM' is running very fast. Can you save ‘The PARAM’ and find the key before RAW agents?
Input
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
1 <= T <= 20
1 <= N <= 100000
Output
Largest Killer number having N digits. If no such number exists, you tell RAW agents that they are wrong and print ‘-1’.
Example
Input: 3 1 3 11 Output: -1 555 55555533333
Explanation
- For N = 1, there is no such number.
- For N = 3, 555 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.
Added by: | Gaurav Jain |
Date: | 2013-09-25 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |