퍼즐

Andrew는 퍼즐 조각을 만드는 공장을 열려고 한다. 그는 판지 시트에서 조각을 잘라낼 특수 장치를 주문해야 한다. 또한 그 장치에 쓸 팁 세트도 주문해야 한다. 각 팁은 특정한 형태의 조각을 자를 수 있다.

퍼즐 조각은 정사각형이고, 네 변 각각에는 둥근 돌기, 빈 홈이 있거나 매끈할 수 있다. 조각은 세 가지 종류가 있다.

• 코너: 매끈한 변 두 개가 서로 인접해 코너를 이루는 조각이다.
• 테두리: 매끈한 변이 정확히 하나인 조각이다.
• 일반: 매끈한 변이 없는 조각이다.

둥근 돌기와 빈 홈은 각각 $k$가지 종류가 있다. 따라서 퍼즐 조각의 한 변에는 $2k+1$가지 선택지가 있다. $k$가지 종류 중 하나인 둥근 돌기, $k$가지 종류 중 하나인 빈 홈, 매끈한 변이다.

Andrew는 팁을 몇 종류 주문해야 하는지 알아내려고 한다. 어떤 조각을 회전시켜 다른 조각과 같아질 수 있다면, 두 조각은 같은 팁으로 자를 수 있다.

가능한 모든 퍼즐 조각을 자를 수 있으려면 Andrew가 몇 종류의 팁을 주문해야 하는지 구하자.

첫째 줄에 정수 $k$가 주어진다. $k$는 둥근 돌기와 빈 홈 종류의 수이다. ($1 \le k \le 10^4$)

Andrew가 주문해야 하는 팁 종류의 수를 출력한다.

$k = 1$일 때의 팁 $18$종류를 아래 그림에 나타냈다.