Cho số nguyên dương ~n~, hãy chia dãy số ~[1^2, 2^2, 3^2, \ldots, n^2]~ thành hai nhóm có tổng bằng nhau.

Input

Dòng đầu tiên chứa số nguyên dương ~t~ (~1 \le t \le 10^3~) — số test case của bài toán.

Mỗi dòng trong ~t~ dòng tiếp theo chứa duy nhất chứa số nguyên dương ~n~ (~1 \le n \le 10^6~).

Dữ liệu đảm bảo tổng của ~n~ trong tất cả các test case không vượt quá ~10^6~.

Output

Với mỗi test case:

• Nếu không tồn tại cách để chia dãy số thành hai nhóm có tổng bằng nhau, in ra NO.

• Ngược lại, in ra YES, sau đó xuống dòng và in ra ~n~ số nguyên ~b_1, b_2, \ldots, b_n~ (~0 \le b_i \le 1~), sao cho ~\sum \limits_{b_i = 0} i^2 = \sum \limits_{b_j = 1} j^2~.

Sample Input 1

2
4
7

Sample Output 1

NO
YES
0 0 1 0 1 1 0