Internet Problem Solving Contest

• Easy input data set – D1
• Hard input data set – D2

Numbers with repeated digits are boring. Look at them: 44 is boring, 474 is boring, 1 000 000 is sooooo boring it hurts.

Numbers without repeated digits aren’t boring at all. As you read such a number, you will always encounter something new! Look: 52 107 is pretty, and 9 087 432 156 is among the most pleasant numbers one can read.

Problem specification

You are given a positive integer n.

Write n in the form a₁ + ⋯ + a_k. Each of the a_i must be a positive integer. The values a_i must not be boring. Their count (i.e., the number k) must be as small as possible.

The values a_i don’t have to be distinct. The same digit may appear in multiple a_i.

Input specification

The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.

Each test case consists of a single line with a single positive integer n.

In the easy subproblem D1 we have t = 1000 and 1 ≤ n ≤ 10 000.

In the hard subproblem D2 we have t = 30 000 and 1 ≤ n ≤ 2 000 000 000.

Output specification

For each test case, output a single line of the form “k a₁ … a_k”.

If there are multiple optimal solutions, you may output any of them.

Example

Input:

3

123

99

999123456

Output:

1 123
2 90 9
2 20469135 978654321