409894: GYM103828 G Little Fermat and digits sums

Little Fermat has recently learned about digits sum. He became super strong that he could solve any problem regarding the sum of digits. Unfortunately, one day he became bored and he started to think about the sum of squares of digits instead of boring simple digits sum. He found that some numbers have amazing properties so he started to call them beautiful numbers! A beautiful number is a natural number that has these two conditions:

1. it doesn't have any zero ($$$0$$$) digit. ($$$174,3,8955$$$ don't have any zero digits while $$$1058,10,600$$$ have at least one zero digits).

2. the sum of the squares of its digits is a perfect square.

A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself.

As Little Fermat became obsessed with these numbers he wants to find a way to generate a beautiful number with $$$n$$$ digits.

Can you help Little Fermat?

The first line of the input contains one integer $$$T$$$ $$$(1 \le T \le 10^5)$$$, the number of test cases.

The next $$$T$$$ lines each contains a single integer $$$n$$$ ($$$1 \le n \le 10^{16}$$$), the number of digits the beautiful number should have.

You are Asked to find any beautiful number with n digits. if there is no such one print $$$ - 1 $$$.

Since the number could be extremely large and the order of digits doesn't matter, you are asked to print $$$9$$$ numbers, which represent the frequencies of the digits $$$1, 2, 3, 4, 5, 6, 7, 8, 9$$$ respectively.

2
1
4

0 0 0 0 0 0 0 0 1 
0 4 0 0 0 0 0 0 0 

In the first test case, $$$9$$$ is a beautiful number with one digit. In the second test case $$$2222$$$ is a beautiful number with four digits