TopCoder

Caido
主唱太拼命了

User's AC Ratio

71.4% (5/7)

Submission's AC Ratio

81.8% (9/11)

Tags

Description

有 $n$ 個人要表演舞蹈,舞台上有 $n$ 個位置,從 $1$ 到 $n$ 編號。

表演會進行 $n$ 個時刻,每個時刻中每個人站的位置都不能相同,且每個人在每個時刻中站的位置也都不能相同。

對於第 $i$ 個人,假設他在這 $n$ 個時刻中分別站在 $a_{i,1},a_{i,2},\ldots,a_{i,n}$ 這個位置的排列,那他對這場演出的有趣程度的貢獻值是

$$\sum_{j=1}^ {n-1} max(a_{i,j}, a_{i,j+1}) \pi + a_{i,j} a_{i,j+1}$$,其中 $\pi$ 是圓周率。

請求出一種能最大化所有人有趣程度之和的站位安排,若有多組可能的解,輸出任何一種即可。

Input Format

輸入第一行有一個正整數 $T$,代表有 $T$ 個子測試資料。

每一筆子測試資料輸入一行,這行有一個正整數 $n$,代表該子測試資料的 $n$。

  • $1\le T\le 100$
  • $2\le n\le 100$

Output Format

對於每一筆子測試資料:

輸出 $n$ 行,代表最大的有趣程度之和對應到的一組可能的構造。

在其中的第 $i$ 行輸出一個 $1$ 到 $n$ 的排列 $a_{i,1},a_{i,2},\ldots,a_{i,n}$ ,代表第 $i$ 個人在每個時間所在的位置。

Sample Input 1

2
2
3

Sample Output 1

1 2
2 1
1 3 2
3 2 1
2 1 3

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0 範例測資。 0
2 0~6 無特別限制。 100

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 262144 65536 1 2
1 1000 262144 65536 2
2 1000 262144 65536 2
3 1000 262144 65536 2
4 1000 262144 65536 2
5 1000 262144 65536 2
6 1000 262144 65536 2