starwars

Time limit: 0.07s Memory limit: 64MB Input: starwars.in Output: starwars.out

Lui Costel i-a plăcut mult filmul "Star Wars", așa că s-a gândit să construiască un droid de latură kk astfel: Va construi 3 platforme de k×kk \times k (câte una peste alta), baza droidului, iar pe margine vor fi două "rânduri" de lungime kk (din câte kk 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 nn. Să se calculeze câte numere pp de la 11 la nn au proprietatea că se poate construi un droid din exact pp blocuri.

Date de intrare

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

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 11 la nn care au proprietatea cerută.

Restricții și precizări

  • 1n1091 \leq n \leq 10 ^ 9
  • Pentru 5050 de puncte, n100 000n \leq 100 \ 000.
  • Pentru alte 2020 de puncte, n10 000 000n \leq 10 \ 000 \ 000.

Exemplu

starwars.in

40

starwars.out

3

Explicație

Cele 33 numere sunt: 55, 1616, 3333.

Log in or sign up to be able to send submissions!