Програмчлалын олимпиадын бодлогын архив

Зураг дээрх дүрсийг авч үзье (жижиг адил талт гурвалжнуудаас тогтсон том адил талт гурвалжин). Энэ зураг дээр дөрвөн түвшинд байрласан жижиг гурвалжнууд байна.

Ийм дүрс дотор хэдэн гурвалжин байгааг тооцоолох програм бич (жижиг гурвалжнуудаас гадна ер нь бүх гурвалжныг тоолно. Жишээ нь тодруулсан гурвалжин болон дүрс бүхэлдээ ч гурвалжинд тооцогдоно).

Input

Оролтын файлд ганц бүхэл тоо N байрлах ба энэ нь дүрс дэх түвшний тоог заана (1 ≤ N ≤ 100000).

Output

Өгөгдсөн  дүрс дэх бүх гурвалжны тоог гаргана.

Example

Input:
1

Output:
1
Input:
2

Output:
5
Input:
4

Output:
27