== include(page="template/taskheader" task_id="matrita") ==

Poveste şi cerinţă...

Plictisit de inmultirea polinoamelor in timp liniar, de rezolvarea conjecturilor sau a altor banalitati precum “Traveling salesman problem”, Nry s-a decis sa porneasca in cautarea secretului fericirii eterne. Privind insa in jurul sau, a constatat cu stupoare ca olimpicii recurg la tehnici necurate in acest joc pentru satisfactie, de la sustrasul subtil al surselor sau al ideilor de probleme, pana la acte mult mai grave, precum insusirea locurilor la IOI sau a editiilor precedente de Junior Challenge. Dorind insa sa fie original (si sa pastreze in acelasi timp noua traditie), Nry a ajuns la urmatoarea concluzie: trebuie sa subtilizeze Matrita!
Odata ajuns in posesia elixirului magic, acesta l-a asezat intr-un colt al Beciului Olimpic (unul din cele mai sigure adaposturi, in care dusmanii pot patrunde doar prin tavanul de sticla). Insa, pentru a se asigura ca noua sa achizitie nu va disparea in mod neasteptat, acesta a decis sa formeze un sistem de aparare in modul urmator: el a privit Beciul ca o matrice patratica de latura $N + 1$ (liniile si coloanele sunt numerodate de la 0 la N), Matrita aflandu-se in patratul aflat pe linia 0 si coloana 0. El doreste sa plaseze mai multe capcane in patrate cu indicii liniilor si ai coloanelor cuprinsi intre $1$ si $N$, astfel incat dreapta care uneste oricare doua capcane sa nu contina Matrita.
Nry va roaga sa raspundeti la urmatoarea intrebare: stiind numarul $N$, in cate moduri isi poate construi el sistemul de aparare al Matritei?
 

h2. Date de intrare

* Pentru alte teste in valoare de 30 de puncte $N ≤ 750.000$
* Pentru alte teste in valoare de 30 de puncte $N ≤ 5.000.000$
* Pentru alte teste in valoare de 10 puncte $N ≤ 10.000.000$

* Legenda spune ca oricine gusta din Matrita are un loc asigurat la IOI 2020

h2. Exemplu