Հավանաբար, ձեզանից շատերը խաղացել են շախմատ: Եվ դուք գիտեք, որ թագուհին կարող է շարժվել ինչպես հորիզոնական և ուղղահայաց ուղղություններով, այնպես էլ անկյունագծերով:

  Արմենը վերջերս սկսել է շախմատով զբաղվել և ինչ-որ տեղ կարդացել է հետևյալ գլուխկոտրուկը, որում պահանջվում է մաքսիմալ թվով թագուհիներ 8x8 շախմատի  տախտակի վրա դասավորել այնպես, որ գոնե մի վանդակ չընկնի հարվածի տակ: Այս խնդիրը շատ հեշտ  է լուծվում 3x3 տախտակի համար: Ակնհայտ է նաև, որ վերը նշված սկզբունքով 2-ից ավելի թագուհի հնարավոր չէ դասավորել տախտակի վրա:

  Օգնե’ք Արմենին լուծել վերը նշված գլուխկոտրուկը nxn տախտակի համար:

Մուտքային տվյալներ

  Մուտքի միակ տողում գրված է n թիվը (1≤n≤100).

Ելքային տվյալներ

  Միակ տողում պետք է արտածել թագուհիների մաքսիմալ քանակը, որը կարելի է դասավորել տախտակի վրա այնպես, որ գոնե մի վանդակ չլինի հարվածի տակ:

Օրինակներ