자르기

시간 제한1초메모리 제한256 MB

요약

주어진 수를 두 개의 비어 있지 않은 수로 잘라 두 수의 차의 절댓값으로 바꾸는 과정을 반복할 때, 도달할 수 있는 가장 작은 수까지의 경로를 출력한다.

난이도: 보통10점 중 7점
유형: 수학, 정수론, 완전 탐색, 구현
정답자: 아직 제출이 없습니다

문제

주어진 수를 두 개의 비어 있지 않은 수로 자르고, 두 수의 차의 절댓값으로 바꿀 수 있다. 이 연산의 결과로 0을 얻는 것은 금지된다. 이러한 자르기는 여러 번 반복할 수 있다. 최종적으로 얻을 수 있는 가장 작은 수를 구해야 한다.

입력

첫 번째 줄에는 테스트의 수 $t$ 가 주어진다.

다음 $t$ 개의 줄에는 각각 하나의 정수 $n$ 이 주어지며, 이는 자르기의 초기 수이다.

출력

각 테스트마다 최솟값을 얻는 경로를 출력해야 한다. 먼저 정수 $m$ 을 출력하는데, 이는 경로에 있는 수의 개수이다. 그런 다음 $m$ 개의 정수를 출력한다. 첫 번째 수는 초기 수이고, 마지막 수는 모든 자르기를 마친 후 얻을 수 있는 최솟값이다. 자르기는 인접한 두 수 사이에서 수행할 수 있어야 한다. 답이 여러 개라면 그중 아무거나 출력한다.

제한

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

예제1

예제 1
입력
```
3
7
100
42
```
예상 출력
```
1 7
2 100 1
2 42 2
```