题目内容

你需要将一个正整数 $n$ 分解成一个整数序列 $a_1, a_2, \dots, a_k$（$k \ge 2$），使得这些数的和等于 $n$，且序列中的每个数只能是 $1$ 或者是大于 $1$ 且不是质数的正整数（即该数存在除了 $1$ 和自身以外的正因子）。要求序列的长度 $k$ 尽可能小。如果存在多种长度最小的方案，你可以输出任意一种。

数据范围：测试数据组数 $T$ 满足 $1 \le T \le 10^3$。每组数据中的 $n$ 满足 $2 \le n \le 10^{18}$。

输入描述

第一行包含一个整数 $T$ $(1 \le T \le 10^3)$，表示测试数据的组数。接下来 $T$ 行，每行包含一个整数 $n$ $(2 \le n \le 10^{18})$，表示需要分解的目标值。

输出描述

对于每组测试数据，输出两行：第一行输出一个整数 $k$，表示你构造的序列长度；第二行输出 $k$ 个整数，用空格分隔，表示序列中的元素。如果有多种满足条件且长度最短的序列，输出任意一种即可。

样例1

输入

3
2
3
5

输出

2
1 1
3
1 1 1
2
1 4

说明

第一组 $n=2$：$2$ 无法拆分为两个合数，只能全部用 $1$，最短长度为 2，序列为 1 1。 第二组 $n=3$：$3$ 同样无法使用合数，最短只能使用 3 个 $1$，序列为 1 1 1。 第三组 $n=5$：$5$ 是奇数，可拆分为 $1$ 和 $4$。$4$ 是大于 $1$ 且不是质数的合数，因此长度为 2，是最短的方案，输出 1 4。

样例2

输入

2
6
9

输出

3
1 1 4
2
1 8

说明

第一组 $n=6$：偶数 $6$ 不能拆成两个合数（例如 $2+4$ 中的 $2$ 是质数），最短需要 3 个数，例如 1 1 4（$4$ 是合数）。 第二组 $n=9$：奇数 $9$ 可拆为 $1$ 和 $8$，$8$ 是合数，因此最短长度为 2，输出 1 8。

样例3

输入

2
100
1000000000000000000

输出

2
4 96
2
4 999999999999999996

说明

第一组 $n=100$：$100$ 是偶数且不小于 $8$，可以构造 $4 + 96$。$4$ 和 $96$ 均为合数，长度为 2 是最优解。 第二组 $n=10^{18}$：这是一个极大的偶数，同样使用 $4$ 和 $n-4$ 的方案，两者都是不小于 $4$ 的偶数合数，长度仍为 2。