==Include(page="template/taskheader" task_id="sah")==

Ciobanasul Eduard are o tabla de sah de dimensiuni $N X N$. El cauta o modalitate de a imparti tabla de sah in cat mai multe regiuni dreptunghiulare (cu laturile paralele cu axele de coordonate) disjuncte, astfel incat toate regiunile sa aibe arii diferite, iar intr-o regiune numarul casutelor albe sa fie egal cu numarul casutelor negre. Deoarece vrea sa se intoarca cat mai repede la oitele sale Eduard va cere voua ajutorul.

Ciobanasul Eduard are o tabla de sah de dimensiuni $NxN$. El cauta o modalitate de a imparti tabla de sah in cat mai multe regiuni dreptunghiulare (cu laturile paralele cu axele de coordonate) disjuncte, astfel incat toate regiunile sa aibe arii diferite, iar intr-o regiune numarul casutelor albe sa fie egal cu numarul casutelor negre. Deoarece vrea sa se intoarca cat mai repede la oitele sale Eduard va cere voua ajutorul.

h2. Cerinta

* $1 ≤ N ≤ 1000$
* $N$ este par
* Fiecare casuta face parte dintr-o singura regiune

* Regiunile trebuie numerotate cu numere consecutive incepand cu $1$

h2. Exemplu

2 3 3 3 |
==Include(page="template/taskfooter" task_id="sah")==

1170