Doraemon quên mất, phải giới thiệu tới các bạn.

Á chết, có một con virus Maisu(Mice) đang hoành hành trong não của Doraemon! Chết, đã sợ chuột, nay còn bị virus Maisu thì Mon 2k(112) đi đời rồi ông giáo à 🙁 Đã vậy, Doraemon còn gặp lại 7 người anh em của mình, rồi biệt đội Doramini nữa, và lại lây con virus này tới những homie của mình. Thật là xui xẻo.

May mắn thay, vẫn còn một cách để cứu sống Doraemon và những người bạn. Virus Maisu sử dụng thuật toán AS(M)R để mã hóa toàn bộ dữ liệu trong não của cậu. Với mỗi con chồn, thuật toán mã hóa sử dụng một mật mã \(M \leq 10^9\). Để giải mã, chúng ta cần tìm ba khóa \(x, y, z\) \((1 \leq x, y, z \leq 2^{60} )\) , sao cho \(x⊕y⊕z=0\), và cả \(x,y\) và \(z\) đều chia hết cho số \(M\). Ở đây \(⊕\) là phép toán thao tác bit XOR.

Nobita với sự trợ giúp của vợ mình là Jaiko, á lộn Shizuka, đã tìm ra một vài số \(M\). Việc của bạn là tìm ra ba ba khóa \(x, y ,z\) bất kỳ để mở khóa và giải mã dữ liệu trong đầu Doraemon hậu đậu.

Các bạn hãy giúp Nô để tương lai Nô không bị Jaian bắt nạt, dẫn tới việc bị cưới Jaiko nhé!

Fact không có thật: Jaiko tương lai ốm nhom và xinh hơn cả Shizuka.

Input

• Dòng thứ nhất chứa một số \(T\) \((1 \leq T \le 10^5)\) là số lượng khóa đã tìm ra.
• Với \(T\) dòng tiếp theo, dòng thứ \(i\) \((1 \leq i \leq T)\) chứa một số \(M_i\) \((1 \leq M_i \leq 10^9)\) là mật mã của chú chồn thứ \(i\).

Output

• Gồm \(T\) dòng, dòng thứ \(i\) \((1 \leq i \leq T)\) chứa ba số \(x_i, y_i, z_i\) \((1 \leq x_i, y_i, z_i < 2^{60})\) là ba khóa dùng để giải mã chú chồn thứ \(i\).

Example

1
5 

80 90 10