Olimpiada de informatică - faza pe școală SEB clasa a 5-a - Mirror | starwars

Lui Costel i-a plăcut mult filmul "Star Wars", așa că s-a gândit să construiască un droid de latură $k$ astfel: Va construi 3 platforme de $k \times k$ (câte una peste alta), baza droidului, iar pe margine vor fi două "rânduri" de lungime $k$ (din câte $k$ blocuri), reprezentând "trăgacii". Platformele și trăgacii vor fi unite, dar niciun bloc nu va aparține unei platforme și unui trăgaci în același timp.

Cerință

Se dă un număr întreg $n$. Să se calculeze câte numere $p$ de la $1$ la $n$ au proprietatea că se poate construi un droid din exact $p$ blocuri.

Date de intrare

Pe prima linie a fișierului de intrare starwars.in se găsește un singur număr natural, $n$.

Date de ieșire

Pe prima linie a fișierului de ieșire starwars.out se va găsi un singur număr întreg, numărul de numere de la $1$ la $n$ care au proprietatea cerută.

Restricții și precizări

• $1 \leq n \leq 10 ^ 9$
• Pentru $50$ de puncte, $n \leq 100 \ 000$.
• Pentru alte $20$ de puncte, $n \leq 10 \ 000 \ 000$.

Exemplu

starwars.in

40

starwars.out

3

Explicație

Cele $3$ numere sunt: $5$, $16$, $33$.