Sau thời gian dài không đến trường thì cây cối ở trường iostream không ai chăm sóc đã trở nên yếu ớt và héo dần.

Nhà trường muốn xây dựng ngôi trường xanh nên đã tổ chức cuộc thi trồng cây. iostream rất hào hứng và đăng ký tham gia ngay lập tức. Thế nhưng khi nghe chi tiết về cuộc thi thì bất lực vì yêu cầu quá rắc rối và phức tạp.

Trường yêu cầu mỗi thí sinh phải trồng được một dãy ~n~ cây với chiều cao lần lượt là ~a_1, a_2, \ldots, a_n~ và phải thỏa mãn các yêu cầu của cuộc thi:

• Chiều cao của mỗi cây phải có dạng ~p^k~ với ~p~ là số nguyên tố bất kỳ và ~k~ là số nguyên không âm.

• Tổng giá trị của tất cả các subsequence của dãy phải đúng bằng ~x~.

Một subsequence của một dãy cây có thể thể thu được bằng cách bỏ đi trong dãy cây đó một số cây bất kì (các cây được bỏ đi không nhất thiết phải liên tiếp). Giá trị một subsequence được tính bằng chiều cao của cây lớn nhất nằm trong subsequence đó, hoặc bằng ~0~ nếu subsequence rỗng.

Bạn hãy giúp iostream tìm ra chiều cao của các cây cần trồng nhé!

Input

• Dòng đầu tiên bao gồm duy nhất một số nguyên ~t~ (~1 \le t \le 1000~) là số lượng số test case.

• Mỗi một test case được mô tả bởi duy nhất một dòng, mỗi dòng chứa duy nhất một số nguyên ~x~ (~1 \le x \le 10^{18})~.

Output

Với mỗi một test case, hãy in ra hai dòng.

• Dòng đầu tiên chứa số ~n~.

• Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, a_3, \ldots, a_n~.

Output cần phải đảm bảo đúng yêu cầu của cuộc thi (trên thực tế, luôn tồn tại ít nhất 1 cách trồng cây thỏa mãn).

Sample Input 1

2
42
30

Sample Output 1

3
5 4 7
2
11 8

Sample Input 2

2
22
130

Sample Output 2

2
9 4
3
11 25 8

Notes

Ở test thứ nhất, test case đầu tiên, các subsequence của output và giá trị tương ứng của chúng được biểu diễn như bảng dưới đây