DepressoEspresso is doing a contest!

This contest has problems worth 1, 2, 5, 10, 20, 50, or 100 points. Given ~N~ point goals for the contest, can you tell DepressoEspresso the minimum number of problems needed to get that exact score and the number of each type of problem that have to be solved?

Input Specification

The first line will contain integer ~N~ ~(1 \leq N \leq 100)~, the number of point goals for this contest.

The next ~N~ lines will contain a single number ~a~ ~(1 \leq a \leq 10^{18})~, the point goal that DepressoEspresso wants to reach.

Output Specification

For every ~N~ value, output the minimum number of problems needed to get the specific value on the first line. On the next line, output the number of each type of problem that have to be done to achieve that exact value, each separated by a single space on the same line.

Sample Input 1

2
7
36

Sample Output 1

2
0 1 1 0 0 0 0
4
1 0 1 1 1 0 0