밤양갱

달디달고, 달디달고, 달디단, 밤양갱, 밤양갱

<장기하, 밤양갱, 2024>

민우는 비비의 신곡 "밤양갱"에 꽂혀 하루 종일 "달디달고 달디달고 달디달고... 달디단"이 머릿속을 맴돌고 있다.

민우의 머릿속에서는 daldidalgo가 $N$번 반복된 뒤, 반복이 끝나면 daldidan으로 끝난다. 예를 들어 $N=3$이라면 민우의 머릿속에서는 daldidalgodaldidalgodaldidalgodaldidan이 재생된다.

민우는 $N$이 주어지면 daldidalgodaldidalgo...daldidan을 컴퓨터에 얼마나 빨리 입력할 수 있는지 궁금하다. 민우는 매초 다음 두 작업 중 하나를 골라 실행할 수 있다.

• 알파벳 소문자 a부터 z 중에서 원하는 알파벳을 하나 골라 지금까지 입력한 문자열의 맨 뒤에 입력한다.
• 지금까지 입력한 문자열의 연속된 부분 문자열을 복사해 입력한 내용의 맨 뒤에 붙여넣는다. 예를 들어 지금까지 작성한 문자열이 ajouapcshake라면 ajouapcshake를 복사할 수도 있고 apc를 복사할 수도 있지만, aashake를 복사하여 붙여넣을 수는 없다.

민우는 몇 초 만에 머릿속에 떠오른 가사를 컴퓨터에 입력할 수 있을까?

첫 번째 줄에 민우의 머릿속에 떠오른 daldidalgo의 횟수 $N$이 주어진다. $(1\leq N \leq 10^9)$

민우가 매초 문제에 언급된 시행 중 하나를 선택해 실행했을 때, daldidalgo를 $N$번 입력한 후 daldidan을 1번 입력하는 데 걸리는 최소 시간을 출력한다.