Zadanie

Andrejova Veľká Veta

Počet bodov: 10, časový limit: 300ms

Určite ste počuli o známej Veľkej Fermatovej Vete: “Neexistujú kladné celé čísla \(a,~b,~c,~n\) také, že \(a^n~+~b^n~=c^n\) pre \(n > 2\).”

Andrej si vymyslel obdobu tejto vety: “Pre každé nezáporné celé číslo \(c\) existuje \(n\) celých čísel \(a_1, \cdots, a_n\) takých, že \(a_1^2 + \cdots + a_n^2 = c\).”

Spokojný s tým, aký je on múdry a tvorivý matematik, išiel spať.

Vy ste však všímaví a Andrejovi matematickú slávu nedoprajete. Veď vôbec nepovedal, aké je to číslo \(n\). Pre niektoré táto veta zjavne neplatí.

Nájdite Andrejovi protipríklady, ktoré mu pokazia ráno.

Vstup a výstup

V jedinom riadku vstupu je celé číslo \(1 \leq n \leq 100\).

Ak existujú nezáporne celé čísla, ktoré sa nedajú získať súčtom práve \(n\) druhých mocnín celých čísel, vypíšte najmenšie z nich (teda najmenšie \(c\), pre ktoré nevieme dostať \(a_1^2 + \cdots + a_n^2 = c\)). Inak vypíšte -1.

Príklady

Input:

1

Output:

2

Môžeme sčítať druhú mocninu len jedného celého čísla. \(0^2 = 0\), \(1^2 = 1\). Nanešťastie, odmocnina dvojky je iracionálne číslo.

Input:

4

Output:

-1

Toto je dôsledok tzv. Lagrangeovej Vety.