Cutting

Time limit1sMemory limit256 MB

Summary

Repeatedly split a number into two non-empty parts and replace it by their nonzero absolute difference; output a shortest path to the smallest reachable value.

Level: Medium7 of 10
Topics: Math, Number theory, Brute force, Implementation
Solved: No attempts yet

Problem

A given number can be cut into two non-empty numbers and replaced with the absolute value of the difference between these two numbers. It is forbidden to obtain zero after such an operation. Such a cut can be repeated several times. It is required to get the minimum possible number in the end.

Input

The first line contains an integer $t$ , the number of tests.

Each of the following $t$ lines contains one integer $n$ , the initial number for cutting.

Output

For each test, you need to output a path to get the minimum number. First print the integer number $m$ , the amount of numbers in the path. Then output $m$ integers. The first number is an initial number, and the last one is the minimum possible number after all cuttings. The cutting must be accomplishable between adjacent numbers. If there are several solutions, output any of them.

Constraints

$1 \le t \le 10^3$
$1 \le n \le 10^{12}$

Examples1

Example 1
Input
```
3
7
100
42
```
Expected output
```
1 7
2 100 1
2 42 2
```