양의 정수 $n$에 대하여, 길이 $n$인 수열이 다음 조건을 만족하면 이를 “붉은 벽돌 수열”이라고 부릅니다:

• $1, 2, \ldots, n$ 각각이 수열에 정확히 한 번씩 등장합니다.
• 인접한 모든 두 원소의 합이 완전제곱수가 아닙니다.

정수 $n$이 주어질 때, 길이 $n$인 붉은 벽돌 수열을 구성하시오.

입력

첫 번째 줄에 테스트 케이스의 개수 $T$ ($1 \le T \le 10^4$)가 주어집니다.

각 테스트 케이스의 유일한 줄에는 구성해야 하는 붉은 벽돌 수열의 길이인 정수 $n$ ($1 \le n \le 4 \times 10^6$)이 주어집니다.

$n$의 합이 $4 \times 10^6$을 초과하지 않음이 보장됩니다. 주어진 제한 조건 아래에서 해가 항상 존재함을 증명할 수 있습니다.

출력

$T$개의 줄을 출력하며, 각 줄에 구성한 수열을 출력합니다. 가능한 답이 여러 개인 경우 그중 아무것이나 출력합니다.

예제

입력 1

5
1
2
3
4
5

출력 1

1
1 2
1 2 3
1 2 3 4
1 4 2 3 5

참고

$n = 5$일 때, 출력한 수열이 1 2 3 4 5라면 $4 + 5 = 9$가 완전제곱수이므로 오답입니다.