A. Паша ба Саваа

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Пашад $n$ эерэг бүхэл тоон урттай модон саваа байна. Тэр савааг дөрвөн хэсэгт хуваахын тулд яг гурван удаа хэрчинэ. Хэсэг бүр эерэг бүхэл тоон урттай байх ёстой ба эдгээр уртуудын нийлбэр мэдээж $n$ байна.

Паша тэгш өнцөгтөд дуртай боловч квадратад дургүй. Тэр хуваасан хэсгүүдийг ашиглан тэгш өнцөгт үүсгэх боломжтой боловч квадрат үүсгэх боломжгүй байхаар савааг дөрвөн хэсэгт хуваах хэдэн зам байх вэ гэж гайхсан.

Таны ажил бол Пашад туслах ба нийт боломжын тоог тоолох юм. Савааг хуваах дараах хоёр арга ялгаатайд тооцогдоно: эхний аргаар хуваасан $x$ урттай хэсгүүдийн тоо хоёр дахь аргаар хуваасан $x$ урттай хэсгүүдийн тооноос ялгаатай байх $x$ бүхэл тоон утга байвал.

Оролт

Оролтын эхний мөрөнд эерэг бүхэл тоон утга $n$ ($1 ≤ n ≤ 2*10^{9}$) байх ба энэ нь Пашагийн савхны урт байна.

Гаралт

Гаралтанд нэг бүхэл тоон утга байх ба хуваасан хэсгүүдийн төгсгөлүүдийг холбон тэгш өнцөгт үүсгэх боломжтой боловч квадрат үүсгэх боломжгүй байхаар Пашагийн савааг эерэг бүхэл тоон урттай дөрвөн хэсэгт хуваах аргын тоо байна.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
6
Гаралт
1
Оролт
20
Гаралт
4

Тэмдэглэл

Эхний жишээн дээр савааг хуваах ганц арга байна {1, 1, 2, 2}.

Хоёр дахь жишээн дээр савааг хуваах дөрвөн арга байна {1, 1, 9, 9}, {2, 2, 8, 8}, {3, 3, 7, 7} ба {4, 4, 6, 6}. Мөн {5, 5, 5, 5} гэж хувааж болохгүйг сана.

Сэтгэгдлүүдийг ачааллаж байна...