Оң бүтін $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$ толық квадрат болып табылады.