Cho số nguyên dương ~n~. Hãy tìm ba số nguyên dương đôi một khác nhau ~a, b, c~ thỏa mãn đồng thời:

• ~a + b + c = n~;
• ~\gcd(a, b) = c~, trong đó ~\gcd(a, b)~ là ước chung lớn nhất của ~a~ và ~b~;
• tích ~a \times b \times c~ lớn nhất có thể.

Dữ liệu

• Dòng đầu tiên chứa số nguyên dương ~t~ (~1 \le t \le 10^5~) là số truy vấn.
• ~t~ dòng tiếp theo, dòng thứ ~i~ chứa một số nguyên dương ~n~ (~1 \le n \le 10^6~) là truy vấn thứ ~i~.

Kết quả

In ra ~t~ dòng, dòng thứ ~i~ gồm ba số nguyên ~a, b, c~ tìm được cho giá trị ~n~ của truy vấn thứ ~i~.

Ví dụ

BOBASO.INP

4
18
63
73
91

BOBASO.OUT

6 9 3
21 35 7
35 37 1
35 49 7

Giới hạn

• Subtask 1 (50% số điểm): ~t \le 10~, ~n \le 5 \times 10^3~.
• Subtask 2 (50% số điểm): không có ràng buộc gì thêm.