Cho trước số nguyên dương ~k~ (~k \leq 10^5~).

Yêu cầu:

• Tìm ước nguyên tố nhỏ nhất của k;
• Tìm tất cả các bộ ba số nguyên tố ~x, y, z~ (~x \leq y \leq z~) sao cho ~x+y+z=k~.

Input

Vào từ file văn bản BAI1.INP chứa số ~k~.

Output

Ghi ra file văn bản BAI1.OUT:

• Dòng thứ nhất ghi ước nguyên tố nhỏ nhất của ~k~. Nếu không tìm được ghi số ~0~;
• Dòng thứ hai ghi ~n~ là số lượng bộ ba số nguyên tố tìm được. ~N~ dòng tiếp theo, mỗi bộ ba số nguyên tố thỏa mãn. Các bộ ba số được ghi theo thứ tự tăng dần của ~x~. Nếu không tìm được bộ ba số thỏa mãn ghi số 0.

Example input 1

10

Example output 1

2
1
2 3 5

Note 1

• Ước nguyên tố nhỏ nhất của 10 là 2.
• Số lượng các bộ số nguyên tố tìm đươc ~n=1~ tương ứng 2, 3, 5.