题目描述

再过几天就是 Alice 的生日，Bob 准备送给 Alice 一件礼物。

每件礼物的偏好程度可以用一个非负整数 $x$ 表示。把 $x$ 写成二进制后，每一位表示 Alice 是否喜欢礼物在某一方面的特征。

Alice 的幸运数字是 $a$，因此 Bob 打算亲手制作一件偏好程度为 $a$ 的礼物。

由于 Bob 的制作技术不够熟练，他只能制作偏好程度为 $3$ 的倍数的礼物。不过，Bob 可以使用一种神秘的方法，将若干件礼物合成为一件新礼物。合成两件礼物后，新礼物的偏好程度等于原来两件礼物偏好程度的按位或。

Bob 准备先制作若干件礼物，再将它们全部合成，使最终礼物的偏好程度恰好为 $a$。

由于合成礼物的难度会随着礼物数量指数级上升，Bob 希望制作的礼物数量尽可能少。

请你求出最少需要制作多少件礼物，并给出一种最优方案。如果无论如何都无法得到偏好程度为 $a$ 的礼物，则输出 $-1$。

输入格式

第一行包含一个整数 $T$，表示测试数据组数。

接下来 $T$ 行，每行包含一个整数 $a$。

输出格式

对于每组测试数据，输出一行。

• 如果无解，输出一个整数 -1。
• 如果有解，首先输出最少需要制作的礼物数量 $c$，随后输出 $c$ 个整数 $b_1,b_2,\ldots,b_c$，表示各件初始礼物的偏好程度。

输出的方案必须满足：

1. 每个 $b_i$ 都是 $3$ 的倍数；
2. $b_1\mathbin{|}b_2\mathbin{|}\cdots\mathbin{|}b_c=a$，其中 $|$ 表示按位或；
3. $c$ 是满足上述条件的最小值。

任意满足要求的最优方案均可被接受。

样例

3
2
3
7

-1
1 3
2 3 6

样例说明

• 对于 $a=2$，不存在满足条件的方案。
• 对于 $a=3$，直接制作一件偏好程度为 $3$ 的礼物即可。
• 对于 $a=7$，可以制作偏好程度分别为 $3$ 和 $6$ 的两件礼物，因为 $3\mathbin{|}6=7$。

数据范围

对于 $100\%$ 的数据：

• $1\le T\le 10^5$；
• $1\le a<2^{60}$。

各子任务的限制如下：