POLSKI SPOJ

Spirala Ulama

Jasiu, znany badacz liczb pierwszych, dzisiaj przygląda się Spirali Ulama. Spirala zaproponowana przez polskiego matematyka Stanisława Ulama to kwadratowa tablica, w której wypisane są spiralnie, w kierunku rotacji przeciwnej do ruchu wskazówek zegara, kolejne liczby od 1 do n², gdzie n jest pewną z góry ustaloną liczbą rozmiaru tablicy. Problem dotyczy głównie grupowania się liczb pierwszych na przekątnych spirali. Jasiu chce także sprawdzić, jak grupują się liczby pierwsze w wierszach spirali. W tym celu potrzebuje pomocy. Dla zadanej wartości n, należy wypisać ciąg n-wyrazowy, w którym i-ty wyraz odpowiada liczebności liczb pierwszych w i-tym wierszu spirali o rozmiarze n.

Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 100) oznaczająca liczbę przypadków testowych. Każdy przypadek to liczba całkowita n (2 ≤ n ≤ 1000) oznaczająca rozmiar tablicy.

Wyjście
Dla każdego przypadku, w osobnym wierszu, należy wypisać ciąg n-wyrazowy, w którym i-ty wyraz odpowiada liczebności liczb pierwszych w i-tym wierszu spirali Ulama o rozmiarze n.

Przykład

Wejście
2
5
6

Wyjście
2 2 3 1 1
1 2 3 3 1 1

Wyjaśnienie dla spirali o rozmiarze 5.

17 16 15 14 13
18  5  4  3 12
19  6  1  2 11
20  7  8  9 10
21 22 23 24 25

W pierwszym wierszu są dwie liczby pierwsze: 17, 13
W drugim wierszu są dwie liczby pierwsze: 5, 3
W trzecim wierszu są trzy liczby pierwsze: 19, 2, 11
W czwartym wierszu jest jedna liczba pierwsza: 7
W piątym wierszu jest jedna liczba pierwsza: 23

Stąd w kolejnych wierszach liczby pierwsze grupują się 2 2 3 1 1.