## IPSC 2017

## Problem D – Dazzling digits

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*_{1} + ⋯ + *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}.

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*_{1} … *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
```