Для додатного цілого числа $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$ є повним квадратом.