普通的二进制分解可以表示为 $n = a_{31}a_{30} \dots a_0$，其中 $a_i \in \{0, 1\}$。

现在有一种奇怪的二进制分解，同样表示为 $n = a_{31}a_{30} \dots a_0$，但需要满足以下条件：

1. 对于 $i = 0, 1, \dots, 31$，$a_i \in \{-1, 0, 1\}$。
2. 对于 $i = 0, 1, \dots, 30$，$a_i$ 和 $a_{i+1}$ 不能同时为 $0$，即 $a_i^2 + a_{i+1}^2 \neq 0$。
3. $$\sum_{i=0}^{31} a_i 2^i = n$$

给定一个非负整数 $n$，求出上述 $n$ 的二进制分解，或者确定它无法被分解。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试用例的数量。

对于每个测试用例，有一行包含一个非负整数 $n$ ($0 \le n < 2^{30}$)，表示需要分解的数字。

输出格式

对于每个测试用例，如果 $n$ 可以被分解，输出字符串 YES，否则输出 NO。

如果第一行输出为 YES，则输出 32 个整数 $a_0, a_1, \dots, a_{31}$，分为 4 行，每行 8 个整数。

样例

输入 1

3
0
3
5

输出 1

NO
YES
1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 1
YES
-1 1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 1