[DSA-ThuatToanSinh].Xếp bài.

Mạnh có N thẻ bài, mỗi thẻ ghi một con số từ 1 tới N. Không có 2 thẻ nào ghi hai số trùng nhau. Mạnh muốn xếp thứ tự các thẻ bài sao cho không có hai con số nào liền kề nhau ở cạnh nhau. Ví dụ với N = 4 thì cách xếp 3142 là hợp lệ nhưng cách xếp 1324 không hợp lệ. Hãy giúp Mạnh liệt kê tất cả các cách xếp thỏa mãn theo thứ tự từ điển.

Input Format

Dòng đầu ghi số bộ test T (không quá 10). Mỗi bộ test ghi số N (3 < N < 10).

Constraints

.

Output Format

Với mỗi bộ test, ghi ra tất cả các cách xếp thứ tự thỏa mãn, mỗi cách trên một dòng.

Ví dụ:

Dữ liệu vào

2
4
5

Dữ liệu ra

2413
3142
13524
14253
24135
24153
25314
31425
31524
35142
35241
41352
42513
42531
52413
53142