34223번 - 하노이 여행하기 스페셜 저지

준혁이와 도훈은 하노이 도시를 걸으며 여행하고 있다. 하노이는 $N$개의 건물이 있으며 $1$부터 $N$까지 번호가 붙어있다.

준혁이는 건물 $a$에서, 도훈은 건물 $b$에서 여행을 시작하여 여행에서 다음과 같은 행동을 $10^{999}$번 반복한다:

• 준혁이가 있는 건물을 $x$, 도훈이 있는 건물을 $y$라고 하자. 순서쌍 $(x,y)$를 종이에 적는다.
• 준혁이는 건물 $A_x$로, 도훈은 건물 $A_y$로 이동한다.

도훈은 소녀 팬들을 위해 여행을 한 이후 종이에 적은 서로 다른 순서쌍의 개수가 최대한 많아지도록 여행을 기획하고 싶다. 두 순서쌍은 첫 번째 원소 혹은 두 번째 원소가 다르다면 다르다.

종이에 적은 서로 다른 순서쌍의 개수를 최대화 하는 두 사람의 시작점 $a$, $b$와 각 건물의 다음 행선지 $A_1, A_2, \ldots, A_N$을 구하여라.

첫째 줄에 테스트케이스의 개수 $t$가 주어진다. $(1 \le t \le 100)$

각 테스트케이스마다 한 줄에 건물의 개수 $N$이 주어진다. $(2 \le N \le 200\,000)$

모든 테스트케이스의 $N$의 합은 $200\,000$을 넘지 않는다.

각 테스트 케이스마다 두 줄을 출력한다.

• 첫째 줄에 $A_1, A_2, \ldots, A_N$을 공백으로 구분하여 출력한다.
• 둘째 줄에 준혁이의 시작 건물 $a$와 도훈의 시작 건물 $b$를 공백으로 구분하여 출력한다.