Problem description


Funkcja Bezkwadratowa
(bezkwadratowa-oc)
Memory limit: 64 MB
Time limit: 5.00 s

Zdefiniujmy f(x) dla dowolnej liczby naturalnej x, jako x podzielony przez największy kwadrat liczby naturalnej, który dzieli x. Np.
f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 1, f(8) = 2, f(16) = 1, f(12) = 3, f(288) = 2
Twoim zadaniem będzie wypisanie wartości f(x) dla każdej liczby naturalnej od 1 do n.

Wejście

W pierwszym i wierszu wejścia znajduje się jedna liczba całkowita n

Wyjście

Wyjście powinno składać się z n wierszy.
W i-tym z nich należy wypisać wartość f(i).

Ograniczenia

0 ≤ n ≤ 107.
Dodatkowo, w testach wartych 20% wszystkich punktów zachodzi zależność n ≤ 2000
Dodatkowo, w innych testach wartych 30% wszystkich punktów zachodzi zależność n ≤ 50 000

Przykład

Input Output Explanation
8
1
2
3
1
5
6
7
2

Największy kwadrat liczby całkowitej przez który dzieli się 4, to 4.
Największy kwadrat liczby całkowitej przez który dzieli się 8, to 4.