Problem description

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 ≤ 10⁷.
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

8

1
2
3
1
5
6
7
2