B. Clock Creation
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Westin is building a clock. He may construct any positive number of gears.

Each gear must receive an integer number of teeth, and every gear must have at least $$$2$$$ teeth. If a gear has $$$x$$$ teeth, it returns to its original position every $$$x$$$ seconds.

All gears rotate together. Starting at time $$$0$$$, every gear advances at a constant rate of 1 tooth per second.

Westin wants that at time $$$k$$$, all gears are simultaneously back in their original positions for the first time.

Among all valid constructions, Westin wants to minimize the total number of teeth used, i.e. $$$a_1 + a_2 + \ldots + a_n$$$ where $$$n$$$ is the number of gears used and $$$a_i$$$ is the number of teeth on gear $$$i$$$.

Determine the minimum possible total number of teeth, and one corresponding construction.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

Each test case contains a single integer $$$k$$$ ($$$2 \le k \le 10^5$$$).

Output

For each test case, output:

  • On the first line, print an integer $$$n$$$ — the number of gears used.
  • On the second line, print $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$a_i \ge 2$$$) describing a construction that achieves the minimum.

If multiple optimal constructions exist, print any.

Example
Input
4
2
12
72
210
Output
1
2 
2
4 3 
2
8 9 
4
2 3 5 7