import sys input = sys.stdin.readline from collections import Counter from math import gcd N=int(input()) LIST=[] for i in range(1,round(N**(1/2))+2): if N%i==0: LIST.append(i) LIST.append(N//i) LIST=sorted(set(LIST)) from functools import lru_cache @lru_cache(maxsize=None) def calc(x): if x==1: return 0 KO=Counter() for i in LIST[::-1]: if i>x: break k=x//i KO[i]+=k for j in LIST: if i%j==0 and j