Ngoài cách chọn quà làm quen như ở phần 1, ta còn có một cách chọn quà là dãy số đầy sáng tạo khác như sau:

Gọi số nguyên $n$ là độ dài của dãy (thoả mãn $n$ lẻ) - món quà bạn muốn tặng thì món quà đó được xem là đẹp nếu tổng của $\lfloor \frac{n + 1}{2} \rfloor$ phần tử bất kì là luôn lớn hơn $\lfloor \frac{n}{2} \rfloor$ phần tử bất kì. Ví dụ các dãy $[2;\ 3;\ 4],\ [5; 6; 7; 8; 9]$ là một món quà đẹp nhưng $[1;\ 3;\ 5;\ 7;\ 8]$ thì không phải.

Nhưng, để món quà không bị coi là nhàm chàn khi có các phần tử lặp lại thì bạn cần chọn món quà sao cho không có hai phần tử nào trùng nhau.

Bạn tuy muốn mua một món quà đẹp và ngầu nhưng lại muốn món quà đó rẻ nhất có thể, giá của một món quà là tổng giá trị các phần tử của món quà đó. Bạn hãy tìm ra món quà thoả mãn điều kiện và có giá rẻ nhất rồi sắp xếp giá trị các phần tử của món quà đó tăng dần và in ra màn hình để chúng mình kiểm tra xem đó có phải món quà tốt nhất bạn có thể mua không nhé. Bạn sẽ được cho $t$ câu hỏi để kiểm tra xem khả năng chọn quà của bạn đã tốt hoàn toàn chưa.

Input

• Dòng đầu tiên gồm số nguyên đương $t(1\leq t\leq 1000)$ - là số câu hỏi mà bạn được cho.
• $t$ dòng tiếp theo mỗi dòng chứa một số nguyên $n$ - độ dài dãy (hay độ dài món quà) mà bạn cần tìm. $(1\leq n\leq 55555)$
• Tổng $n$ trong các câu hỏi luôn bé hơn hoặc bằng $55555$.

Ouput

• Gồm $t$ dòng với mỗi dòng là dãy con (hay món quà) bạn tìm được cũng chính câu trả lời cho câu hỏi tương ứng.

Subtasks

• Bài tập này không có subtask nào.

Example

2
3
5

2 3 4
5 6 7 8 9