有 $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$ 是圓周率。
請求出一種能最大化所有人有趣程度之和的站位安排,若有多組可能的解,輸出任何一種即可。
輸入第一行有一個正整數 $T$,代表有 $T$ 個子測試資料。
每一筆子測試資料輸入一行,這行有一個正整數 $n$,代表該子測試資料的 $n$。
對於每一筆子測試資料:
輸出 $n$ 行,代表最大的有趣程度之和對應到的一組可能的構造。
在其中的第 $i$ 行輸出一個 $1$ 到 $n$ 的排列 $a_{i,1},a_{i,2},\ldots,a_{i,n}$ ,代表第 $i$ 個人在每個時間所在的位置。
No. | Testdata Range | Constraints | Score |
---|---|---|---|
1 | 0 | 範例測資。 | 0 |
2 | 0~6 | 無特別限制。 | 100 |