31629번 - 가지의 정령 사사

문제

한 변의 길이가 양의 정수인 정사각형 모양의 가지밭에는 가지의 정령 사사의 힘이 깃들어 정말 맛있는 가지가 자라납니다. 이런 가지밭에는 특정 길이의 가지만 자랄 수 있다는 전승이 내려오는데, 한 변의 길이가 $n$일 때 자랄 수 있는 가지의 길이는 다음과 같이 결정된다고 합니다.

• $n \times n$ 크기의 비어있는 표를 두 개 준비합니다.
• 하나의 표에는 맨 위의 가로줄에 왼쪽에서 오른쪽 순서로 1ドル$부터 $n$까지 채워 넣습니다. 그 아래 가로줄에는 $n+1$부터 2ドルn$을 순서대로 채워 넣습니다. 이를 반복하여 1ドル$부터 $n^2$까지의 모든 수를 써넣습니다.
• 다른 하나의 표에는 맨 위 왼쪽 칸에 1ドル$을 씁니다. 그다음, 맨 왼쪽 세로줄의 둘째 가로줄부터 위 오른쪽 대각선으로 올라가면서 다음 수를 차례로 씁니다. 그다음, 맨 왼쪽 세로줄의 셋째 가로줄부터 위 오른쪽 대각선으로 올라가면서 다음 수를 차례로 씁니다. 이와 같이 반복하다가 가장 오른쪽 위 칸이 채워진 후로는 가장 왼쪽 아래 칸의 오른쪽 칸부터 시작해서 위 오른쪽 대각선으로 올라가면서 수를 채웁니다. 이를 반복하여 1ドル$부터 $n^2$까지의 모든 수를 써넣습니다.
• 두 표에서 같은 위치에 같은 수가 등장하는 경우가 있음을 확인할 수 있습니다. 그 수들이 그 가지밭에서 자랄 수 있는 가지의 길이입니다.

그림 1그림 1

$n = 6$인 가지밭을 예로 들면 다음과 같습니다. 우선, 그림 1-a, 1-b와 같이 두 개의 6ドル \times 6$ 표를 만듭니다. 그런 다음, 그림 1-c와 같이 두 표를 겹치면 1ドル,ドル 9ドル,ドル 28ドル,ドル 36ドル$이 두 표의 같은 위치에서 나타나는 것을 알 수 있습니다. 따라서 이 가지밭에는 길이가 1ドル,ドル 9ドル,ドル 28ドル,ドル 36ドル$인 가지만 자랄 수 있습니다.

키위새는 가지를 너무나 사랑한 나머지 자신만의 가지밭을 갖고 싶어 합니다. 키위새는 가지밭의 한 변의 길이가 될 수 있는 후보들을 정해뒀는데, 자랄 수 있는 가지의 길이를 계산하는 데 어려움을 겪고 있습니다. 키위새를 도와 가지밭의 한 변의 길이가 주어지면 자랄 수 있는 가지의 길이를 출력하는 프로그램을 작성해 봅시다.

입력

첫 번째 줄에 키위새가 후보로 둔 가지밭 크기의 가짓수 $T$가 주어집니다. $(1 \le T \le 100)$

다음 $T$개 줄 각각에 키위새가 답을 알고 싶은 가지밭의 한 변의 길이 $n$이 주어집니다. 같은 $n$이 두 번 이상 입력으로 주어지는 경우는 없습니다. $(1 \le n \le {10}^9;$ $n$은 정수$)$

출력

$T$개의 줄에 걸쳐 한 변의 길이가 $n$인 정사각형 가지밭에 자랄 수 있는 모든 가지 길이를 공백으로 구분하여 한 줄에 출력합니다. 가지의 길이는 오름차순으로 하여 출력합니다.

제한

힌트